一,各排序算法的思想及其稳定性
以下排序算法的排序结果若无特殊说明均为升序,swap函数的具体实现如下,每次的排序算法不再重复。(吐槽:多年后的今天来看,尼玛,都忘了,看不懂了!真佩服自己)
void swap(int *a, int i, int j) //交换两个数 { if(i==j) return; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }
1,八大经典排序算法
(1)冒泡排序
依次比较相邻的数据,将小数据放在前,大数据放在后;即第一趟先比较第1个和第2个数,大数在后,小数在前,再比较第2个数与第3个数,大数在后,小数在前,以此类推则将最大的数"滚动"到最后一个位置;第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。
以下面5个无序的数据为例:
40 8 15 18 12 (文中仅细化了第一趟的比较过程)
第1趟: 8 15 18 12 40
第2趟: 8 15 12 18 40
第3趟: 8 12 15 18 40
第4趟: 8 12 15 18 40
void bubblesort(int *arr,int nsize) { //排序,从i开始排,总是在[i+1,nsize]去寻找比当前元素小的,并且交换,使得当前位置的值总是其后面最小的。 for (int i = 0; i < nsize; i++) for (int j = i + 1; j < nsize; j++) if (arr[i] > arr[j]) swap(arr, i,j); }
(2)选择排序
以升序为例,比如在一个长度为N的无序数组中,
在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,
第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......
第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,
至此选择排序完成。
以下面5个无序的数据为例:
56 12 80 91 20(文中仅细化了第一趟的选择过程)
第1趟:12 56 80 91 20
第2趟:12 20 80 91 56
第3趟:12 20 56 91 80
第4趟:12 20 56 80 91
核心函数:
void selectsort(int *arr, int nsize) { for (int i = 0; i < nsize; i++) { //arr[i+1....nsize-1]中找到当前最小值及其位置(准备与当前a[i]调换) int min = arr[i]; int minpos = i; for (int j = i + 1; j < nsize; j++) { if (arr[j] < min) { min = arr[j]; //当前最小值 minpos = j;//记录当前最小值的位置 } } swap(arr, i, minpos);//交换最小值位置,a[0....i]已经有序 } }
tip:
冒泡法和选择排序很像,两者区别在于:
冒泡排序是每一次都可能要交换,而选择排序是在比较时记下a[i]的位置 最后来交换
所以他们的交换过程是不一样的,但查找的过程是一样的。
所以选择排序的效率比冒泡法只高不低...
(3)插入排序
像扑克摸牌一样,插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。例如有一个长度为N的无序数组,进行N-1次的插入即能完成排序;第一次,数组第1个数认为是有序的数组,将数组第二个元素插入仅有1个有序的数组中;第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中......第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完成了整个插入排序。
以下面5个无序的数据为例:
65 27 59 64 58 (文中仅细化了第四次插入过程)
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
void insertsort(int *arr, int nsize) { int i, j, key; for (i = 1; i<nsize; i++)//控制需要插入的元素 { key = arr[i]; //key为当前要插入的元素,将其插入到有序段arr[0,i-1] j = i - 1; while (j >= 0 && arr[j] > key) //查找要插入的位置,循环结束时则找到插入位置j { arr[j+1] = arr[j]; //移动元素的位置.供要插入元素使用 j--; } arr[j+1] = key; //插入指定元素到指定位置 } }
(4)快速排序
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,该方法的基本思想是:
1.先从数列末尾取出一个数作为基准元。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
//手动快速默写快排:先划界,再分治....
int quickPartion(int *arr, int low, int high) { int pos = rand() % (high - low + 1) + low; swap(arr, pos, high);//将末尾的元素随机化,防止极端情况 int key = arr[high];//总是将末尾元素选为关键化界元 int i = low - 1;//总是记录比key小的元素最前面的位置 for (int j = low; j <= high - 1; j++) { if (arr[j] <= key) swap(arr, ++i, j); } swap(arr, ++i, high); return i;//返回“中间位置” } void QuickSort(int *arr, int low, int high) { if (low < high) { int mid = quickPartion(arr, low, high); QuickSort(arr, low, mid - 1); QuickSort(arr, mid + 1, high); } }
(5)归并排序
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。
核心函数:
//分治法的合并函数 //arr[low...mid]与arr[mid+1...high]相合并 void Merge(int *arr, int low, int mid, int high) { int leftlen = mid - low + 1;//arr[low...mid]的长度 int rightlen = high - mid;//arr[mid+1...high]的长度 int *L = new int[leftlen + 1];//每次归并时都在动态申请内存,这里可以优化 int *R = new int[rightlen + 1]; L[leftlen] = INT_MAX;//末尾均是哨兵元素 R[rightlen] = INT_MAX; //赋值,准备有序放入arr[low.....high] int i = 0; for (; i < leftlen; i++) L[i] = arr[low + i]; int j = 0; for (; j < rightlen; j++) R[j] = arr[mid + j + 1]; //有序放入arr[low.....high] i = 0; j = 0; for (int k = low; k <= high; k++) { if (L[i] <= R[j])//谁更小,谁就放入arr[k]中 arr[k] = L[i++]; else arr[k] = R[j++]; } delete[] L; L = NULL; delete[] R; R = NULL; } //合并排序法(分治法) void MergeSort(int *arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; MergeSort(arr, low, mid); MergeSort(arr, mid + 1, high); Merge(arr, low, mid, high); } }
(6)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
//希尔排序 void ShellSort(int *a,int nlen) { int gap = nlen ; while (gap>1) { gap = gap / 3 + 1; for (int i = gap; i < nlen; ++i) { int temp = a[i]; //暂存关键数据 int j = i; while (j - gap >= 0 && temp < a[j - gap]) { a[j] = a[j - gap]; //后移 j = j - gap; //前置索引 } a[j] = temp; } } }
(7)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。
//保持堆的性质 //在数组arr中以位置i为入口维护最大堆性质(根节点总是更大) void KeepMaxHeap(int *a, int i, int heapsize) //使a[i]这个元素下降(如果不满足最大根要求的话) { int l = 2*i+1; int r = 2*i+2; //找到当前入口位置i及其左右子之间的较大者,如果不是当前i位置的值最大,将会交换并重新开始调整 int largest =i; if (l <= heapsize && a[l]>a[i])//与左子比 largest = l; if (r <= heapsize && a[r]>a[largest])//将较大者与右子比 largest = r; if (largest != i) { swap(a,i,largest); KeepMaxHeap(a, largest, heapsize); } } //创建堆,将数组调整为最大堆 void BuildMaxHeap(int *a,int nsize) { int heapsize = nsize - 1; for (int i = heapsize / 2; i >= 0; i--) KeepMaxHeap(a, i, heapsize);//heapsize/2+1到a.size-1的整数都是树叶,所以只需对0到heapsize/2作处理 } //堆排序 void HeapSort(int *a,int nsize) { BuildMaxHeap(a,nsize);//使数组成为最大堆 int heapsize = nsize-1; for (int i = nsize - 1; i>0; i--) { swap(a,0, i); heapsize--;//叶子将逐渐“脱离” KeepMaxHeap(a, 0, heapsize);//保持堆的性质 } }
(8)计数排序
假设数序列中小于元素a的个数为n,则直接把a放到第n+1个位置上。当存在几个相同的元素时要做适当的调整,因为不能把所有的元素放到同一个位置上。计数排序假设输入的元素都是0到k之间的整数。
计数排序算法没有用到元素间的比较,它利用元素的实际值来确定它们在输出数组中的位置。因此,计数排序算法不是一个基于比较的排序算法,从而它的计算时间下界不再是Ω(nlogn)。
对每一个输入元素x,确定小于x的元素的个数,那样排序之后,x在最终输出数组中的位置就可以确定了。
例如:如果有17个元素小于x,则x就位于第18个输出的位置上。
//计数排序 void CountSort(int *a, int len) { int nLen = len; int* Cout = new int[nLen]; //申请空间,用于计数,被排序的数一定要是[0,nLen-1]之间的数(可包括) //初始化记数为0 for (int i = 0; i < nLen; ++i) Cout[i] = 0; //统计元素出现次数计数。即数组元素a[i]的出现次数,将其结果存放在Cout[a[i]]中。 for (int i = 0; i < nLen; ++i) ++Cout[a[i]]; //统计小于等于当前位置i的元素个数 for (int i = 1; i < nLen; ++i) Cout[i] += Cout[i - 1]; int* Sort = new int[nLen]; //申请空间,用于存放排序结果 for (int i = 0; i < nLen; ++i) { //把数据放在指定位置。因为pCout[pData[i]]的值就是不比他大数据的个数。 //为什么要先减一,因为pCout[pData[i]]保存的是不比他大数据的个数中包括了 //他自己,我的下标是从零开始的!所以要先减一。 --Cout[a[i]]; //因为有相同数据的可能,所以要把该位置数据个数减一。 Sort[Cout[a[i]]] = a[i]; } //排序结束,复制到原来数组中。 for (int i = 0; i < nLen; ++i) a[i] = Sort[i]; //释放申请的空间。 delete[] Cout; Cout = NULL; delete[] Sort; Sort = NULL; }
2,排序算法小结
综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,
而冒泡排序、插入排序、计数排序、归并排序和基数排序是稳定的排序算法。还有一些排序算法我没有进行
二,C++模板实现
1,程序说明
1),本程序实现了若干经典排序算法性能(运行时间)比较
2),实现了在不同规模(元素个数)下的性能比较
3),实现了对移动次数和比较次数的统计(间接说明性能)
4),实现了数据混乱类型的选择
注:本程序有可能有bug,非绝对正确,发现过错误,未调试完!
2,AllSort.h代码如下
#include "iostream" #include "vector" using namespace std; template<class DataType> class AllSort { public: AllSort() { //移动次数初始化 countSortMove=0; //比较次数初始化 countSortCmp=0; //初始化数据时的不重复个数 countNum=5; } ~AllSort() { } //打印数组 void printArray(vector<DataType> &a,bool isPrint); //交换元素 void swap(DataType *a,DataType *b); //初始化数组 void InitArr(vector<DataType> &a,int len,int arrType); //冒泡排序法 void BubbleSort(vector<DataType> &a, int l, int r, bool Up=true); //插入排序法 void InsertSort(vector<DataType> &a, int l, int r, bool Up=true); //快速排序法 void QuickSort(vector<DataType> &a, int l, int r, bool Up=true); //划界 int Partition(vector<DataType> &a, int l, int r, bool Up=true); //随机快速排序法 void RandQuickSort(vector<DataType> &a, int l, int r, bool Up=true); //随机划界 int RandPartition(vector<DataType> &a, int l, int r, bool Up=true); //三者取中快速排序法 void thrWayQuickSort(vector<DataType> &a, int l, int r, bool Up=true); //三者取中划界 int thrWayPartition(vector<DataType> &a, int l, int r, bool Up=true); //分而治之排序法 void MergeSort(vector<DataType> &a, int l, int r, bool Up=true); void Merge(vector<DataType> &a, int p, int q, int r,bool Up=true); //计数排序 void CountSort(vector<DataType> &a,int arrType,int len,bool Up=true); //洗牌策略随机打乱一个数组中的n个元素 void randArray(vector<DataType> &a, unsigned int n,int isRand); //选择排序法 void SelectSort(vector<DataType> &a, int l, int r, bool Up=true); //希尔排序 void ShellSort(vector<DataType> &a,int low, int high,bool Up=true); //堆中的左子 int Left(int i); //堆中的右子 int Right(int i); //保持堆性质 void KeepMaxHeap(vector<DataType> &a, int len,int heapsize,bool Up); //建堆 void BuildMaxHeap(vector<DataType> &a,bool Up); //堆排序 void HeapSort(vector<DataType> &a,bool Up); int getSortCount(bool IsMove) { if (IsMove) { return countSortMove; }else { return countSortCmp; } } void beforSort() { //移动次数初始化 countSortMove=0; //比较次数初始化 countSortCmp=0; } private: //移动次数 int countSortMove; //比较次数 int countSortCmp; //初始化数据时的不重复数据个数 int countNum; }; //交换元素 template <typename DataType> void AllSort<DataType>::swap(DataType *a,DataType *b) { DataType temp; temp =*a; *a=*b; *b=temp; } //交换元素 template <typename DataType> void AllSort<DataType>::InitArr(vector<DataType> &a,int len,int arrType) { if (arrType == 1) { for (int i=0;i<len;i++) { a.push_back(i); } }else if(arrType == 2) { for (int i=0;i < len;i++) { int key=i%countNum; a.push_back(key); } } } // 随机打乱一个数组n个元素 template <typename DataType> void AllSort<DataType>::randArray(vector<DataType> &a,unsigned int n,int isRand) { if ( n > a.size() ) { cerr<<"无法打乱指定数量的元素"<<endl; exit(1); } if (isRand == 1)//随机打乱 { unsigned int index, i; for (i = 0; i < n; i++)//将数组中的每一个元素都进行随即打乱 { index = rand() % n;//残生0到n-1之间的随机位置数 if (index != i) { swap(&a[i],&a[index]); } } }else if(isRand == 2)//升序 { bool upflag=true; this->ShellSort(a,0,a.size()-1,upflag); }else if(isRand == 3) //降序 { bool upflag=false; this->ShellSort(a,0,a.size()-1,upflag); }else if(isRand == 4) { unsigned int gap=5; unsigned int index, i; for (i = 0; i < n; i++)//将数组中的每一个元素都进行随即打乱 { index = rand()%gap + i;//残生i到j之间的随机位置数 if ( index != i&& index < n) { swap(&a[i],&a[index]); } } }else { cerr<<"isRand参数错误!来自randArray()函数"<<endl; return; } } //打印数组 template <typename DataType> void AllSort<DataType>::printArray(vector<DataType> &a,bool isPrint) { if (isPrint) { cout<<"排序或打乱结果为: "; for(unsigned int i = 0; i < a.size(); i++ ) { cout << a[ i ]<<" "; if ((i+1)%27 == 0) { cout<<endl; } } cout<<endl; } } //希尔排序 template <typename DataType> void AllSort<DataType>::ShellSort(vector<DataType> &a,int low, int high,bool Up) { beforSort(); int gap = high-low+1; while (gap>1) { gap = gap/3+1; for(int i = low + gap; i <= high; ++i) { int temp = a[i]; //暂存关键数据 int j = i; countSortCmp++; if (Up) { while(j-gap >= low && temp < a[j-gap]) { a[j] = a[j-gap]; //后移 j = j-gap; //前置索引 countSortCmp++; countSortMove++; } }else { while(j-gap >= low && temp > a[j-gap]) { a[j] = a[j-gap]; //后移 j = j-gap; //前置索引 countSortCmp++; countSortMove++; } } a[j] = temp; countSortMove=countSortMove+2; } } } //随机快速排序划界函数 int stepRandQuickSort=1; template <typename DataType> void AllSort<DataType>::RandQuickSort(vector<DataType> &a, int low, int high, bool Up) { int pivotKey=0; if ( stepRandQuickSort ==1) { beforSort(); stepRandQuickSort=0; } if (low < high) { pivotKey=RandPartition(a,low,high,Up); RandQuickSort(a,low,pivotKey-1,Up); RandQuickSort(a,pivotKey+1,high,Up); } } //随机快速排序的中点函数 template <typename DataType> int AllSort<DataType>::RandPartition(vector<DataType> &a, int low, int high, bool Up) { int randPivotKey=rand()%(high-low+1)+low; this->swap(&a[randPivotKey],&a[high]); countSortMove=countSortMove+3; return Partition(a,low,high,Up); } int stepthrWayQuickSort=1; template <typename DataType> void AllSort<DataType>::thrWayQuickSort(vector<DataType> &a, int low, int high, bool Up) { if (stepthrWayQuickSort ==1) { beforSort(); stepthrWayQuickSort=0; } int pivotKey=0; if (low < high) { pivotKey=thrWayPartition(a,low,high,Up); thrWayQuickSort(a,low,pivotKey-1,Up); thrWayQuickSort(a,pivotKey+1,high,Up); } } //快速排序的中点函数 template <typename DataType> int AllSort<DataType>::thrWayPartition(vector<DataType> &a, int low, int high, bool Up) { int PivotKey1=rand()%(high-low+1)+low; int PivotKey2=rand()%(high-low+1)+low; int PivotKey3=rand()%(high-low+1)+low; int midkey=PivotKey1; if (PivotKey1 <= PivotKey2 && PivotKey2 <= PivotKey3 ) { midkey=PivotKey2; countSortCmp=countSortCmp+2; }else if( PivotKey2 <= PivotKey1 && PivotKey1 <= PivotKey3 ) { midkey=PivotKey1; countSortCmp=countSortCmp+2; }else { midkey=PivotKey3; } this->swap(&a[midkey],&a[high]); countSortMove=countSortMove+3; return Partition(a,low,high,Up); } //快速排序 int stepQuickSort=1; template <typename DataType> void AllSort<DataType>::QuickSort(vector<DataType> &a, int low, int high, bool Up) { if (stepQuickSort ==1) { beforSort(); stepQuickSort=0; } int mid=0; if (low < high) { mid=Partition(a,low,high,Up); QuickSort(a,low,mid-1,Up); QuickSort(a,mid+1,high,Up); } } //快速排序的划界函数 template <typename DataType> int AllSort<DataType>::Partition(vector<DataType> &a, int low, int high, bool Up) { int pivotkey=a[high];//选择主元,即基准元素 int i=low-1; if (Up) { for ( int j = low;j < high;j++) { countSortCmp++; if (a[j] < pivotkey && i != j ) { i++; swap(&a[i],&a[j]); countSortMove=countSortMove+3; } } }else { for ( int j = low;j < high;j++) { countSortCmp++; if (a[j] > pivotkey) { i++; swap(&a[i],&a[j]); countSortMove=countSortMove+3; } } } i++; swap(&a[i],&a[high]); countSortMove=countSortMove+3; return i; } int stepMerge=1; //合并排序法(分治法) template <typename DataType> void AllSort<DataType>::MergeSort(vector<DataType> &a, int low, int high, bool Up) { if (stepMerge==1) { beforSort(); stepMerge=0; } if (low < high) { int mid=(low+high)/2; MergeSort(a,low,mid,Up); MergeSort(a,mid+1,high,Up); Merge(a,low,mid,high,Up); } } //分治法的合并函数 template <typename DataType> void AllSort<DataType>::Merge(vector<DataType> &a, int low, int mid, int high,bool Up) { int n1=mid -low+1,n2=high-mid; long Max=99999999; long Min=-99999999; int *L=new int[n1+1]; int *R=new int[n2+1]; if ( L == NULL || R == NULL ) { exit(1); } int i=0; for ( ;i < n1;i++ ) { L[i]=a[low+i]; countSortMove++; } int j=0; for ( ;j < n2;j++ ) { R[j]=a[mid+j+1]; countSortMove++; } i=0;j=0; int k=0; if (Up) { L[n1]=Max;//哨兵元素位置 R[n2]=Max; for ( k = low; k <= high ; k++ ) { if ( L[i] <= R[j] ) { a[k]=L[i]; i++; countSortMove++; }else { a[k]=R[j]; j++; countSortMove++; } countSortCmp++; } }else { L[n1]=Min;//哨兵元素位置 R[n2]=Min; for ( k = low; k <= high ; k++ ) { if ( L[i] >= R[j] ) { a[k]=L[i]; i++; countSortMove++; }else { a[k]=R[j]; j++; countSortMove++; } countSortCmp++; } } delete[] L; delete[] R; } //选择排序法 template <typename DataType> void AllSort<DataType>::SelectSort(vector<DataType> &a, int low, int high, bool Up) { beforSort(); DataType min; DataType max; for(int i = low ; i <= high; i++) { //找到最小值及其位置(准备与a[i]调换) min = a[i]; max = a[i]; int index = i; for(int j=i+1;j <= high;j++) { countSortCmp++; if (Up) { if(a[j] < min) { min = a[j]; //当前最小值 index = j;//当前最小值的位置 countSortMove++; } }else { if(a[j] > max) { max = a[j]; //当前最大值 index = j;//当前最大值的位置 countSortMove++; } } } if (Up) { swap(&a[i],&a[index]); countSortMove=countSortMove+3; }else { swap(&a[i],&a[index]); countSortMove=countSortMove+3; } } } //冒泡排序 template <typename DataType> void AllSort<DataType>::BubbleSort(vector<DataType> &a, int l, int r, bool Up) { beforSort(); bool flag=false; for ( int i = l;i < r;i++) { flag=false; for ( int j = r;j >= i+1;j--) { countSortCmp++; if (Up) { if (a[j-1]>a[j]) //调换次序 { this->swap(&a[j-1],&a[j]); countSortMove=countSortMove+3; flag=true; } }else { if (a[j-1]<a[j]) { this->swap(&a[j-1],&a[j]); countSortMove=countSortMove+3; flag=true; } } } if (!flag) { break; } } } //插入排序 template <typename DataType> void AllSort<DataType>::InsertSort(vector<DataType> &a, int l, int r, bool Up) { beforSort(); DataType key; if (Up) { for ( int i = l+1 ; i <= r;i++ ) { key=a[i]; int j=i-1; countSortCmp++; while ( j >= l && a[j] > key ) { a[j+1]=a[j]; j--; countSortMove++; countSortCmp++; } a[j+1]=key; countSortMove=countSortMove+2; } } else { for ( int i = l+1 ; i <= r;i++ ) { key=a[i]; int j=i-1; countSortCmp++; while (j >= l && a[j] < key) { a[j+1]=a[j]; j--; countSortMove++; countSortCmp++; } a[j+1]=key; countSortMove=countSortMove+2; } } } template <typename DataType> int AllSort<DataType>::Left( int i) { return 2*i+1; } template <typename DataType> int AllSort<DataType>::Right( int i) { return 2*i+2; } //保持堆的性质 template <typename DataType> void AllSort<DataType>::KeepMaxHeap(vector<DataType> &a, int i,int heapsize,bool Up) //使a[i]这个元素下降(如果不满足最大根要求的话) { int l=Left(i); int r=Right(i); int largest=0; int min=0; if (Up) { if (l<= heapsize && a[l]>a[i])//与左子比 { largest=l; } else { largest=i; } if (r<= heapsize && a[r]>a[largest])//将较大者与右子比 { largest=r; } }else { if (l<= heapsize && a[l]<a[i])//与左子比 { min=l; } else { min=i; } if (r<= heapsize && a[r]<a[min])//将较大者与右子比 { min=r; } } countSortCmp=countSortCmp+2; if (Up) { if (largest!=i) { swap(&a[i],&a[largest]); countSortMove=countSortMove+3; KeepMaxHeap(a,largest,heapsize,Up); } }else { if (min!=i) { swap(&a[i],&a[min]); countSortMove=countSortMove+3; KeepMaxHeap(a,min,heapsize,Up); } } } //创建堆,将数组调整为最大堆 template <typename DataType> void AllSort<DataType>::BuildMaxHeap(vector<DataType> &a,bool Up) { int heapsize=a.size()-1; for (int i=heapsize/2 ; i>=0 ;i-- ) { KeepMaxHeap(a,i,heapsize,Up);//heapsize/2+1到a.size-1的整数都是树叶,所以只需对0到heapsize/2作处理 } } //堆排序 template <typename DataType> void AllSort<DataType>::HeapSort(vector<DataType> &a,bool Up) { beforSort(); BuildMaxHeap(a,Up);//使数组成为最大堆 int heapsize=a.size()-1; for (int i=a.size()-1;i>0;i--) { swap(&a[0],&a[i]); countSortMove=countSortMove+3; heapsize--; KeepMaxHeap(a,0,heapsize,Up);//保持堆的性质 } } //计数排序 template <typename DataType> void AllSort<DataType>::CountSort(vector<DataType> &a,int arrType,int len,bool Up) { int nLen=len; int k=0; if (arrType==1) { k=nLen; }else { k=countNum; } countSortCmp=0; DataType* Cout = new DataType[nLen]; //申请空间,用于计数 //初始化记数为0 for (int i = 0; i < k; ++i) { Cout[i] = 0; } //统计元素出现次数计数。即数组元素a[i]的出现次数,将其结果存放在Cout[a[i]]中。 for (int i = 0; i < nLen; ++i) { ++Cout[a[i]]; } //统计小于等于当前位置i的元素个数 for (int i = 1; i < nLen; ++i) { Cout[i] += Cout[i - 1]; } DataType* Sort =new DataType[nLen]; //申请空间,用于存放排序结果 for (int i = 0; i < nLen; ++i) { //把数据放在指定位置。因为pCout[pData[i]]的值就是不比他大数据的个数。 //为什么要先减一,因为pCout[pData[i]]保存的是不比他大数据的个数中包括了 //他自己,我的下标是从零开始的!所以要先减一。 --Cout[a[i]]; //因为有相同数据的可能,所以要把该位置数据个数减一。 Sort[Cout[a[i]]] = a[i]; } //排序结束,复制到原来数组中。 if (Up==true) { for (int i = 0; i < nLen; ++i) { a[i] = Sort[i]; } }else { for (int i = 0; i < nLen; ++i) { a[i] = Sort[nLen-i-1]; } } //释放申请的空间。 delete[] Cout; Cout=NULL; delete[] Sort; Sort=NULL; } 3,主测试代码: [html] view plain copy print? // ConsoleAppAllSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "iostream" #include <vector> #include <windows.h> #include "AllSort.h" #include "stdio.h" #include<algorithm> #include<functional> using namespace std; LARGE_INTEGER freq; LARGE_INTEGER startTime, stopTime; double time; void help(int len,bool Up,int IsRand,int arrType); void initArr(); int _tmain(int argc, _TCHAR* argv[]) { system("color 0A"); AllSort<int> sort;//定义排序类对象 vector<int> arr; //定义并初始化一个容器,进行数组操作 int len=10; //控制数组长度 char ans='y'; do { cout<<"请输入数组初始化类型及元素个数:(1为元素完全不重复,2为有大量重复值)"<<endl; int arrType=1;//1为完全不重复,2为大量重复值 cin>>arrType>>len; sort.InitArr(arr,len,arrType); //各大开关 cout<<"请输入排序类型:0为降序,1为升序"<<endl; bool upflag=false;//控制所有排序的升排或者降排的开关 cin>>upflag; cout<<"请输入数组的随机类型:1为纯随机,2为升序,3为降序,4为小随机"<<endl; int isRand=1;//1为纯随机,2为升序,3为降序,4为小随机 cin>>isRand; cout<<"是否打印排序结果:0为否,1为是"<<endl; bool isPrint=false;//是否print cin>>isPrint; bool isMove=true; help(len,upflag,isRand,arrType); cout<<"/**************************改进冒泡法***************************/"<<endl; sort.randArray(arr,len,isRand); sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.BubbleSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/*******************std::sort()(注:无法统计次数)******************/"<<endl; sort.beforSort(); sort.randArray(arr,len,isRand); sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); if (upflag) { std::sort(arr.begin(),arr.end(),std::less<int>()); }else { std::sort(arr.begin(),arr.end(),std::greater<int>()); } QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/**************************插入法***************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.InsertSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/**************************分治法***************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.MergeSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/********************快排法(随机划界元)**********************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.RandQuickSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/********************快排法(三数取中划界元)*******************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.thrWayQuickSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/********************快排法(尾端划界元)*************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.QuickSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/*****************************选择法****************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.SelectSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/******************************希尔法***************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.ShellSort(arr,0,arr.size()-1,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/******************************堆排序法***************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.HeapSort(arr,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"/******************************计数序法***************************/"<<endl; sort.randArray(arr,len,isRand);//打乱数组 sort.printArray(arr,isPrint); QueryPerformanceCounter(&startTime); sort.CountSort(arr,arrType,len,upflag); QueryPerformanceCounter(&stopTime); sort.printArray(arr,isPrint); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"消耗时间"<<time<<"毫秒 "; cout<<"移动次数:"<<sort.getSortCount(isMove)<<" 比较次数"<<sort.getSortCount(!isMove)<<endl; cout<<"是否继续(y/n)?"<<endl; cin>>ans; arr.clear(); } while (ans=='y'); system("pause"); return 0; } void help(int len,bool Up,int IsRand,int arrType) { cout<<"/***********************综上所述******************************"<<endl; cout<<"当前数组元素个数为:"<<len<<endl; cout<<"原始数组的元素特点:"<<endl; if (arrType==1) { cout<<" 1)无重复值"<<endl; cout<<" 2)值分布:0-"<<len-1<<endl; }else if(arrType==2) { cout<<" 1)大量重复值"<<endl; cout<<" 2)非重复值的分布:0-5"<<endl; } if (IsRand == 1) { cout<<" 3)随机分布"<<endl; }else if(IsRand ==2) { cout<<" 3) 有序:升序"<<endl; }else if(IsRand ==3) { cout<<" 3) 有序:降序"<<endl; } else if(IsRand ==4) { cerr<<" 3) 小随机(总体上呈有序趋势)"<<endl; }else { cerr<<"IsRand参数错误!"<<endl; } if (Up) { cout<<"各排序即将执行:升序"<<endl; }else { cout<<"各排序即将执行:降序"<<endl; } QueryPerformanceFrequency(&freq); QueryPerformanceCounter(&startTime); Sleep(500); QueryPerformanceCounter(&stopTime); time = 1e3*(stopTime.QuadPart-startTime.QuadPart)/freq.QuadPart; cout<<"你电脑的频率为:"<<freq.QuadPart<<endl; cout<<"你的电脑执行Sleep(500)消耗时间为:"<<time<<"毫秒"<<endl; }
三,测试结果
(篇幅有限,仅展示部分结果)
四,总结:
1、冒泡排序
优点:稳定; 思想易理解,编写简单
缺点:慢,每次只能移动相邻两个数据。
2、选择排序
优点:编写简单;移动数据的次数已知(n-1次);
缺点:比较次数多。
3、插入排序
优点:稳定,思想简单,编写简单。
缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
4、希尔排序
优点:快,数据移动少;
缺点:不稳定,gap的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取,并且无法对链表排序。
5、快速排序
快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。
优点:极快,数据移动少;
缺点:不稳定。
6、归并排序
归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
归并排序:归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。
7、堆排序:
由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:
一是建堆,二是交换数值(或者输出堆),三是排序(调整堆)。
所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。
8、计数排序:
对于数组元素集中在小范围内的整数数组排序特别快,并且也是稳定排序,但是这种排序算法缺点特别大。
参考资源:
【1】《算法导论》
【2】《维基百科》
【3】《百度文库》
【4】http://www.oschina.NET/question/1397765_159365
【5】http://www.cnblogs.com/biyeymyhjob/archive/2012/07/17/2591457.html
【6】http://blog.csdn.Net/xiazdong/article/details/8462393
【7】http://baike.baidu.com/view/297739.htm
【8】http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html
【9】http://blog.csdn.net/hguisu/article/details/7776068
【10】http://blog.csdn.net/speedme/article/details/23021467
注:
本文部分文字参考并整理自网络,代码参考并改编自算法导论.
微信
支付宝