数据结构与算法之: 排序 (十一)
影响排序算法性能的几个要素
-
时间性能
-
辅助空间
-
算法的复杂性
冒泡排序
冒泡排序的基本思想
两两相邻记录的关键字,如果反序则交换,直4到没有反序的记录为止Code
void BubbleSort(int k[],int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=n-1;j>i;j--)
{
if(k[j-1] > k[j])
{
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
}
}
}
}冒泡排序的要点
-
两两注意是相邻的两个元素的意思
-
如果有n个元素需要比较n-1次,每一轮减少1次比较
优化
void BubbleSort(int k[],int n)
{
int i,j,temp,flag;
flag = 1;
for(i=0;i<n-1&&flag;i++)
{
flag = 0;
for(j=n-1;j>i;j--)
{
if(k[j-1] > k[j])
{
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
flag = 1;
}
}
}
}选择排序
选择排序的基本思想
选择排序算法就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换Code
#include <stdio.h>
void SelectSort(int k[],int n)
{
int i,j,min,temp;
for(i=0;i<n-1;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(k[j]<k[min])
{
min = j;
}
}
if(min!=i)
{
temp = k[min];
k[min] = k[i];
k[i] = temp;
}
}
}直接插入排序
直接插入排序的基本思想
直接插入排序算法(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增加1的有序表Code
void InsertSort(int k[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
if(k[i] < k[i-1])
{
temp = k[i];
for(j=i-1;k[j] > temp;j--)
{
k[j+1] = k[j];
}
k[j+1] = temp;
}
}
}希尔排序
Code
void ShellSort(int k[],int n)
{
int i,j,temp;
int gap = n;
do
{
gap = gap/3 + 1;
for(i=gap;i<n;i++)
{
if(k[i] < k[i-gap])
{
temp = k[i];
for(j=i-gap;k[j] > temp;j-gap)
{
k[j+gap] = k[j];
}
k[j+gap] = temp;
}
}
}while(gap > 1)
}堆排序
要点
根节点一定是堆中所有节点最大或者最小的,如果按照层序遍历的方式给节点从1开始编号,则结点之间满足如下关系
ki >= k2i ki <= k2i
或 (1<=i<=floor(n/2))
ki >= kv(2i+1) ki <= kv(2i+1)堆排序(Heap Sort)就是利用堆进行排序的算法,它的基本思想是:
-
将待排序的序列构造成一个大顶堆(或小顶堆)
-
此时,整个序列的最大值就是堆顶的根节点.将它移走(就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值)
-
然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的最大值
-
如此反复执行,便能得到一个有序序列
Code
void swap(int k[],int i,int j)
{
int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
void HeapAdjust(int k[],int s,int n)
{
int i;
for(i=2*s;i<=n;i*=2)
{
if(i<n && k[i]<k[i+1])
{
i++;
}
if(temp >= k[i])
{
break;
}
k[s]= k[i];
s = i;
}
k[s] = temp;
}
//数组从1开始
void HeapSort(int k[],int n)
{
int i;
for(i=n/2;i>0;i--)
{
HeapAdjust(k,i,n);
}
for(i=n;i>1;i--)
{
(k,1,i);
HeapAdjust(k,1,i-1);
}
}归并排序
归并排序的基本思想
归并排序(Merge Sort)就是利用归并的思想实现的排序方法.它的原理是假设初始记录有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到ceil(n/2)个长度为2或1的有序子序列;再两两归并,......,如此重复,直到得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序.
Code
/*
递归实现
*/
#define MAXSIZE 10
//实现归并并把结果存入list1
void merging(int *list1,int list1_size,int *list2,int list2_size)
{
int i,j,k,m;
int temp[MAXSIZE];
i = j = k = 0;
while(i<list1_size && j<list2_size)
{
if(list1[i]<list2[j])
{
temp[k++] = list1[i++];
}
else
{
temp[k++] = list2[j++];
}
}
while(i<list1_size)
{
temp[k++] = list1[i++];
}
while(j<list2_size)
{
temp[k++] = list2_size[j++];
}
for(m=0;m<(list1_size + list2_size);m++)
{
list1[m] = temp[m];
}
}
void MergeSort(int k[],int n)
{
if(n>1)
{
int *list1 = k;
int list1_size = n/2;
int *list2 = k+n/2;
int list2_size = n - list1_size;
MergeSort(list1,list1_size);
MergeSort(list2,list2_size);
merging(list1,list1_size,list2,list2_size);
}
}/*
迭代实现
*/
void MergeSort(int k[],int n)
{
int i,left_min,left_max,right_min,right_max;
int *temp = (int*)malloc(n*sizeof(int));
for(i=1;i<n;i*=2)
{
for(left_min=0;left_min<n-i;left_min=right_max)
{
right_min = left_max = left_min + i;
right_max = left_max + i;
if(right_max > n)
{
right_max = n;
}
int next = 0;
while(left_min < left_max && right_min < right_max)
{
if(k[left_min] < k[right_min])
{
temp[next++] = k[left_min];
}
else
{
temp[next++] = k[right_min];
}
}
while(left_min < left_max)
{
k[--right_min] = k[--left_min];
}
while(next > 0)
{
k[--right_min] = temp[--next];
}
}
}
}快速排序
Code
void swap(int k[],int low,int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[],int low,int high)
{
int point;
point = k[low];
while(low<high)
{
while(low<high && k[high] >= point)
{
high--;
}
swap(k,low,high);
while(low<high && k[low] <= point)
{
low++;
}
swap(k,low,high);
}
return low;
}
void QSort(int k[],int low,int high)
{
int point;
if(low < high)
{
point = Partition(k,low,high);
QSort(k,low,point-1);
QSort(k,point+1,high);
}
}
void QuickSort(int k[],int n)
{
QSort(k,0,n-1);
}快速排序的优化
优化选取基准点
选取三个元素中排在中间的元素int m = low + (high-low)/2;
if(k[low] > k[high])
{
swap(k,low,high);
}
if(k[m] > k[high])
{
swap(k,m,high);
}
if(k[m] > k[low])
{
swap(k,m,low);
}优化不必要的交换
int Partition(int k[],int low,int high)
{
int point;
int m = low + (high-low)/2;
if(k[low] > k[high])
{
swap(k,low,high);
}
if(k[m] > k[high])
{
swap(k,m,high);
}
if(k[m] > k[low])
{
swap(k,m,low);
}
point = k[low];
while(low<high)
{
while(low<high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while(low<high && k[low] <= point)
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return low;
}优化小数组时的排序方案
- 小规模时使用直接插入排序
#define MAX_LENGTH_INSERT_SORT 7
void ISort(int k[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
if(k[i] < k[i-1])
{
temp = k[i];
for(j=i-1;k[j] > temp;j--)
{
k[j+1] = k[j];
}
k[j+1] = temp;
}
}
}
void InsertSort(int k[],int low,int high)
{
ISort(k+low,high-low+1);
}
void swap(int k[],int low,int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[],int low,int high)
{
int point;
int m = low + (high-low)/2;
if(k[low] > k[high])
{
swap(k,low,high);
}
if(k[m] > k[high])
{
swap(k,m,high);
}
if(k[m] > k[low])
{
swap(k,m,low);
}
point = k[low];
while(low<high)
{
while(low<high && k[high] >= point)
{
high--;
}
k[low] = k[high];
while(low<high && k[low] <= point)
{
low++;
}
k[high] = k[low];
}
k[low] = point;
return low;
}
void QSort(int k[],int low,int high)
{
int point;
if(high - low > MAX_LENGTH_INSERT_SORT)
{
point = Partition(k,low,high);
QSort(k,low,point-1);
QSort(k,point+1,high);
}
else
{
InsertSort(k,low,high);
}
}
void QuickSort(int k[],int n)
{
QSort(k,0,n-1);
}优化递归操作
- 什么是尾递归?
如果一个函数中递归形式的调用出现在函数的末尾,我们成这个递归函数是尾递归的
当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的.编译器可以做到这一点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了.通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,使得实际的运行效率会变得更高.因此,只要有可能我们就需要将递归函数写成尾递归的形式
void QSort(int k[],int low,int high)
{
int point;
if(high - low > MAX_LENGTH_INSERT_SORT)
{
while(low < high)
{
point = Partition(k,low,high);
if(point -low < high - point)
{
QSort(k,low,point-1);
low = point + 1;
}
else
{
QSort(k,point+1,high);
high = point - 1;
}
}
}
else
{
InsertSort(k,low,high);
}
} 总结
算法分类
算法特点
- 浅色为基本算法,深色为改进算法
