首页 > 代码库 > C++排序算法小结
C++排序算法小结
近期来闲来无事，整理了一些比较常见的排序算法，都是用C++写的，其中包括：直接插入排序、折半插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、希尔排序、基数排序，计数排序和桶排序，总共11种算法，其中时间复杂度为O(n^2)为前4种，中间4中的时间复杂度为O(nlgn)，最后3种的时间复杂度为O(n)。下面我们分3个栏目来介绍:n^2排序、nlgn排序和线性排序。
注：A为全局变量，为一维int数组
n^2排序
直接插入排序
类似于扑克牌排序的原理，在斗地主的时候，每当摸到一张牌后就插入到相应的位置，直接插入排序就是这个原理。从数组第一个数开始，比较该数和前面的数的大小，如果前面的数比该数小，则和前面一位的数调换位置，然后继续比较，直到出现一个数比该数小为止。
核心代码如下：
1 void InsertSort() 2 { 3 int i,j; 4 for(i = 1;i <= N;i++) 5 { 6 j = i; 7 while(j > 0 && A[j] < A[j - 1]) 8 { 9 swap(A[j],A[j-1]);10 j --;11 }12 } 13 }
折半插入排序
其实这种算法是直接插入排序的一种优化，在一个数与其前面的数字进行比较的时候，取以数组第一个数和该数前一个数为区间的中间的数，类似与二分法。
核心代码如下：
1 void HalfSort() 2 { 3 int i, j, high, low, mid; 4 for (i = 2; i <= N; i++) 5 { 6 A[0] = A[i]; 7 low = 1; 8 high = i - 1; 9 while (low <= high)10 {11 mid = (low + high) / 2;12 if (A[0] < A[mid])13 high = mid - 1;14 else15 low = mid + 1;16 }17 for (j = i - 1; j >= high + 1; j--)18 A[j + 1] = A[j];19 A[high + 1] = A[0];20 }21 }
冒泡排序
这个排序算法算是我最早接触的算法，原理就是每次内循环一遍就能把最小的数排到前面，这样外循环完后就排好了。
核心算法如下：
1 void BubbleSort() 2 { 3 for(int i = 1;i <= N - 1;i++) 4 { 5 for(int j = N;j >= i+1;j--) 6 { 7 if(A[j] < A[j - 1]) 8 swap(A[j],A[j-1]); 9 }10 }11 }
选择排序
和冒泡排序类似，只不过是先找到最小的数的下标，然后再置换到相应的位置。
核心代码如下：
1 void SelectSort() 2 { 3 int i,j,lowkey,lowindex; 4 for(i = 1;i <= N - 1;i++) 5 { 6 lowindex = i; 7 lowkey = A[i]; 8 for(j = i + 1;j <= N;j++) 9 {10 if(A[j]<lowkey)11 {12 lowkey = A[j];13 lowindex = j;14 }15 }16 swap(A[i],A[lowindex]);17 }18 }
nlgn排序
快速排序
这个排序算法在nlgn排序算法中算是比较常见的算法了，速度快而且可以进行不同程度的优化。
算法原理概括为2部分：
•分解：数组A[i..j]被划分为两个(可能为空)子数组A[i..q-1]和A[q+1..j]，使得A[i..q-1]中没一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..j]中每一个元素。其中，计算下标q也是划分过程的一部分;
•解决：通过递归调用快速排序，对子数组A[i..q-1]和A[q+1..j]进行排序;
返回合适的主元下标，这里是用数组从左到右两个不同的数偏大的为主元：
1 int FindPivot(int i,int j) 2 { 3 int firstkey = A[i]; 4 int k; 5 for (k = i + 1; k <= j; k++) 6 { 7 if (A[k] > firstkey) 8 return k; 9 else if (A[k] < firstkey)10 return i;11 }12 return 0;13 }
划分部分代码：
1 void Patition(int i, int j, int q) 2 { 3 int pivot = A[q]; 4 int l = i; 5 int r = j; 6 do 7 { 8 swap(A[l],A[r]); 9 while(A[l] < pivot) l++;10 while(A[r] >= pivot) r--; 11 }while(l <= r);12 }
排序代码：
1 void QuickSort(int i, int j) 2 { 3 int q,l,r,pivot; 4 q = FindPivot(i,j); 5 if (q != 0) 6 { 7 Patition(i,j,q); 8 QuickSort(i,l-1); 9 QuickSort(l,j);10 }11 }
C++排序算法小结