这些经典排序，你必须掌握

排序，算法最基础的体现之一。程序员必备的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序等。

排序的本质在于交换，各类排序算法的不同也仅局限于交换的方式和次数，所以，理解排序，要先理解交换。

1.冒泡排序

思想：类似于水中的气泡上浮的过程，较小的气泡先冒起，较大的气泡后冒起。依次比较相邻的两个数，将比较大的数字放在右边。

原理：每次通过交换的方式把当前剩余元素的最大值移动到一端，而剩余的元素为0时，排序结束。

代码描述：

#include<iostream>using namespace std;int main(){ char A[10]={1,2,4,5,6,43,7,9,3,5}; for(int i=1;i<10;i++){ for(int j=0;j<10-i;j++) { //第i趟从A[0]到A[10-i-1]都与下一个数进行比较 if(A[j]>A[j+1]){ //交换使得本趟的最大值在最右边 int temp = A[j]; A[j]=A[j+1]; A[j+1]=temp; } } } for(int i=0;i<10;i++){ printf('%d ',A[i]); } return 0;}

分析：排序过程执行n-1趟，每一趟从左到右比较相邻的两个数，如果大的数在左边，则交换这两个数，当该趟排序完成后，剩余数的最大值在最右边。

时间复杂度：O(n²)

空间复杂度：O(1)

2.选择排序

思想：此处的选择排序是简单选择排序，就是从未排序的序列中找出最大（小）值放到有序序列。

原理：先从未排序的序列中找出最大（小）元素放在排序序列的起始位置，然后再从未排序序列中再次寻找，以此类推，直到所有的元素均已排序。

代码描述：

#include<iostream>using namespace std;int main(){  char A[10]={1,2,4,5,6,43,7,9,3,5};  for(int i=1;i<10;i++){    int min=i;//令未排序序列第一个值为最小值     //依次比较每一个未排序的值，找出其中的最小值     for(int j=i+1;j<10;j++){      if(A[j]<A[min])        min=j;    }     //交换最小值到当前位置     int temp = A[i];    A[i]=A[min];    A[min]=temp;  }  for(int i=0;i<10;i++){    printf('%d ',A[i]);  }  return 0;}

分析：对一个序列A中的元素A[i]~A[n]，令i从1到n枚举,进行n趟操作,每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。于是在n趟操作后，所有元素就会是有序的。总共需要进行n趟操作(1≤i≤n)，每趟操作选出待排序部分[i,n]中最小的元素，令其与A[i]交换。

时间复杂度：O(n²)

空间复杂度：O(1)

3.插入排序

思想：此处的插入排序为最简单的直接插入排序，将一个元素，插入有序队列的合适位置，使得插入后的序列依旧有序。

原理：将待插入元素一个个插入初始已有序部分中的过程，而插入位置的选择遵循了使插入后仍然保持有序的原则，具体做法一般是从后往前枚举已有序部分来确定插入位置。

代码描述：

#include<iostream>using namespace std;int main(){ char A[10]={1,2,4,5,6,43,7,9,3,5}; for(int i=1;i<10;i++){ int temp=A[i];//temp存放将要排序的数 int j=i; //j从i开始往前枚举 while(j>0&&temp<A[j-1]){//将要排序的数与前面的每一个数进行比较，若将要插入的数较小将其向前面移动； A[j]=A[j-1];//将较大的数字向后移 j--; } A[j]=temp;//A[j]是找到的将要插入的位置，将temp插入 } for(int i=0;i<10;i++){ printf('%d ',A[i]); } return 0;}

分析：对序列A的n个元素A[0]~A[n-1]，令i从1到n-1枚举，进行n-1趟操作。假设某一时，序列A的前i个元素A[0]~A[i]已经有序，而范围[i+1,n]还未有序，那么该从范围[0,i]中寻找某个位置j，使得将A[i+1]插入位置j后（此时A[j]~A[i]会后移一位至A[j+1]~A[i+1]），范围[0,i+1]有序。

时间复杂度：O(n²)

空间复杂度：O(1)

4.归并排序

思想：此处的归并排序为最基本的2-路归并排序，将序列分成若干组，组内排序完成后，再合并为一个有序序列。

原理：将序列两两分组，将序列归并为[n/2]个组，组内单独排序；然后将这些组再两两归并，生成[n/4]个组，组内再单独排序；以此类推，直到只剩下一个组为止。

代码描述：

#include<cstdio> const int maxn = 100; //将数组A的[L1,R1]和[L2,R2]区间合并为有序区间（此处L2即为R1+1） void merge(int A[],int L1,int R1,int L2,int R2) {  int i=L1,j=L2; //i指向A[l1],j指向A[L2]  int temp[maxn],index = 0; //temp临时存放合并后的数组，index为其下标   while(i<=R1&&j<=R2){    if(A[i]<=A[j]) {  //如果A[i]<=A[j]       temp[index++]=A[i++];  //将A[i]加入序列temp     }else{    // 如果A[i]>A[j]       temp[index++]=A[j++];    //将A[j]加入序列temp     }  }   while(i<=R1) temp[index++] = A[i++];  //将[L1,R1]的剩余元素加入序列temp   while(j<=R2) temp[index++] = A[j++];  //将[L2,R2]的剩余元素加入序列temp   for(i=0;i<index;i++){    A[L1+i] = temp[i];    //将合并后的序列赋值回数组A   }} //将array数组当前区间[left,right]进行归并排序void mergeSort(int A[],int left,int right) {  if(left<right){    //只要left<right      int mid = (left+right)/2;  //取[left,right]的中点     mergeSort(A,left,mid);  //递归，将左子区间[left,mid]归并排序      mergeSort(A,mid+1,right);  //递归，将右子区间[mid+1,right]归并排序      merge(A,left,mid,mid+1,right);  //将左子区间和右子区间合并   }}int main(){  const int n=10;  int A[n] = {1,2,4,5,6,43,7,9,3,5};  mergeSort(A,0,n-1);   for(int i=0;i<n;i++){    printf('%d ',A[i]);  }  return 0;}#include<cstdio>const int n=10;//对区间[left,right]进行划分int Partition(int A[], int left, int right) {  int temp = A[left];    //将主元（A[left]）存放至临时变量temp   while(left<right) {    //只要left和right不相遇     while(left<right&&A[right]>temp) right--;    //比较主元和从右侧开始遍历的元素，元素大于主元则左移     A[left] = A[right];      //元素不大于主元，将此元素A[right]挪到A[left]     while(left<right&&A[left]<=temp) left++;    //比较主元和从左侧开始遍历的元素，元素小于等于主元则右移     A[right] = A[left];      //元素大于主元，将此元素A[left] 挪到A[right]  }  A[left] = temp;    //把temp放到left与right相遇的地方   return left;     //返回相遇的下标 } //快速排序，left与right初值为序列首位下标（例如1与n）void quickSort(int A[],int left,int right) {  if(left<right) {    //将[left,right]按A[left]一分为二    int pos = Partition(A,left,right);    quickSort(A,left,pos-1);  //对左子区间递归进行快速排序     quickSort(A,pos+1,right);  //对右子区间递归进行快速排序   }} int main(){  int A[n]={1,2,4,5,6,43,7,9,3,5};  quickSort(A,0,9);  for(int i=0;i<n;i++){    printf('%d ',A[i]);  }  return 0;}

分析：其核心在于如何将两个有序序列合并成一个有序序列。

时间复杂度：O(nlogn)

空间复杂度：O(n)

5.快速排序

思想：调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素、右侧所有元素均大于该元素，对该元素的左侧和右侧进行相同的操作，直至当前调整区间的长度不超过1。

原理：对一个序列A[1]、A[2]、…、A[n]，调整序列中元素的位置，使得A[1](原序列的A[1]，下同)的左侧所有元素都不超过A[1]、右侧所有元素都大于A[1]。例如对序列{5,3,9,6,4,1}来说，可以调整序列中元素的位置，形成序列{3,1,4,5,9,6}，这样就让A[1]=5左侧的所有元素都不超过它、右侧的所有元素都大于它。

代码描述：

#include<cstdio>const int n=10;//对区间[left,right]进行划分int Partition(int A[], int left, int right) { int temp = A[left]; //将主元（A[left]）存放至临时变量temp while(left<right) { //只要left和right不相遇 while(left<right&&A[right]>temp) right--; //比较主元和从右侧开始遍历的元素，元素大于主元则左移 A[left] = A[right]; //元素不大于主元，将此元素A[right]挪到A[left] while(left<right&&A[left]<=temp) left++; //比较主元和从左侧开始遍历的元素，元素小于等于主元则右移 A[right] = A[left]; //元素大于主元，将此元素A[left] 挪到A[right] } A[left] = temp; //把temp放到left与right相遇的地方 return left; //返回相遇的下标 } //快速排序，left与right初值为序列首位下标（例如1与n）void quickSort(int A[],int left,int right) { if(left<right) { //将[left,right]按A[left]一分为二 int pos = Partition(A,left,right); quickSort(A,left,pos-1); //对左子区间递归进行快速排序 quickSort(A,pos+1,right); //对右子区间递归进行快速排序 }} int main(){ int A[n]={1,2,4,5,6,43,7,9,3,5}; quickSort(A,0,9); for(int i=0;i<n;i++){ printf('%d ',A[i]); } return 0;}

分析：其关键在于主元的选取，我们将数组的第一个元素即A[left]定为主元，其实这样是不合理的，会导致时间复杂度出现及其不合理的差距甚至达到最坏的时间复杂度O(n²)。正确的方法是随机选取主元。

时间复杂度：O(nlogn)

空间复杂度：O(nlogn)

拓展：
根据[left,right]生成的随机数进行主元的选取：

#include<cstdio>#include<cstdlib>#include<ctime>#include<cmath>#include<cstring>using namespace std;const int n=10;//交换函数 void swap(int &a,int &b){  int temp=0;  temp = b;  b=a;  a=temp;}//对区间[left,right]进行划分int Partition(int A[], int left, int right) {  //生成[left,right]内的随机数p  int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));   swap(A[p],A[left]);  int temp = A[left];    //将主元（A[left]）存放至临时变量temp   while(left<right) {    //只要left和right不相遇     while(left<right&&A[right]>temp) right--;    //比较主元和从右侧开始遍历的元素，元素大于主元则左移     A[left] = A[right];      //元素不大于主元，将此元素A[right]挪到A[left]     while(left<right&&A[left]<=temp) left++;    //比较主元和从左侧开始遍历的元素，元素小于等于主元则右移     A[right] = A[left];      //元素大于主元，将此元素A[left] 挪到A[right]  }  A[left] = temp;    //把temp放到left与right相遇的地方   return left;     //返回相遇的下标 } //快速排序，left与right初值为序列首位下标（例如1与n）void quickSort(int A[],int left,int right) {  if(left<right) {    //将[left,right]按A[left]一分为二    int pos = Partition(A,left,right);    quickSort(A,left,pos-1);  //对左子区间递归进行快速排序     quickSort(A,pos+1,right);  //对右子区间递归进行快速排序   }} int main(){    int A[n]={1,2,4,5,6,43,7,9,3,5};    quickSort(A,0,9);  for(int i=0;i<n;i++){    printf('%d ',A[i]);  }  return 0;}

声明：以上部分知识点参考自《算法笔记》。