本文共 4991 字，大约阅读时间需要 16 分钟。

最近在准备考研，正好在学习数据结构的排序，发现下面这位大佬总结的很详细，不过是用java，我得用c++来考试，所有用c++来总结一下。

大多图片均来自于：

作者：一像素

c++代码学习：天勤考研

1.冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；3.针对所有的元素重复以上的步骤，除了最后一个；4.重复步骤1~3，直到排序完成。

代码：

#include 
   
    using namespace std;void bubleSort(int arr[],int n){
       int i,j,flag;    for(i=0;i
    
     arr[j+1])            {
                   swap(arr[j],arr[j+1);                flag=1;            }        }        //如果flag等于0,证明排序已经完成，不需要继续排序        if(flag==0)            return;    }}//打印void printLn(int arr[],int n){
          for(int i=0;i
    
   

2.插入排序

当遍历元素为i时，依次与它前面的i-1,i-2等比较大小。当遇到元素小于遍历元素时，循环停止，记录遍历元素i应该插入的位置。

代码：

#include 
   
    using namespace std;void insertSort(int arr[],int n){
       for( int i = 1 ; i < n ; i ++ ) {
           int e=arr[i];        int j; // j保存元素e应该插入的位置        for (j = i; j > 0 && arr[j-1] > e; j--)            arr[j] = arr[j-1];        arr[j] = e;    }}//打印void printLn(int arr[],int n){
          for(int i=0;i
   

3.简单选择排序

每次遍历依次找出最小值，放到最前面，然后继续找出它后面剩余元素的最小值，直到剩余元素只有一个时，遍历完成。

代码：

#include 
   
    using namespace std;void selectSort(int arr[],int n){
       int i,j,k;    for(i=0;i
    
     arr[j])                k=j;        swap(arr[i],arr[k]);    }}//打印void printLn(int arr[],int n){
          for(int i=0;i
    
   

4.希尔排序

图片地址：

#include 
   
    using namespace std;void shellSort(int arr[],int n){
       int temp;    for(int gap=n/2;gap>0;gap/=2)    {
           for(int i=gap;i
    
     =0;j-=gap){
                   if(arr[j]>arr[j+gap])                {
                       int temp=arr[j];                    arr[j]=arr[j+gap];                    arr[j+gap]=temp;                }            }        }    }}//打印void printLn(int arr[],int n){
          for(int i=0;i
    
   

5.快速排序

1.从数列中挑出一个元素，称为 “基准”。2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码：

#include
   
    using namespace std;void quickSort(int arr[],int low,int high){
       int temp;    int i=low,j=high;    if(low
    
     =temp)                --j;            if(i
    
   

快速代码的改进：

#include
   
    using namespace std;int _partition(int arr[],int l,int r){
       int v=arr[l];    int j=l;    for(int i=l+1;i<=r;i++){
           if(arr[i]
    
     =r)        return ;    int p=_partition(arr,l,r);    _quickSort(arr,l,p-1);    _quickSort(arr,p+1,r);}void quickSort(int arr[],int n){
       _quickSort(arr,0,n-1);}//打印void printLn(int arr[],int n){
          for(int i=0;i
    
   

6.归并排序

#include
   
    using namespace std;// 将arr[l...mid]和arr[mid+1...r]两部分进行归并void _merge(int arr[], int l, int mid, int r){
       int aux[r-l+1];    for( int i = l ; i <= r; i ++ )        aux[i-l] = arr[i];    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1    int i = l, j = mid+1;    for( int k = l ; k <= r; k ++ ){
           if( i > mid ){
     // 如果左半部分元素已经全部处理完毕            arr[k] = aux[j-l]; j ++;        }        else if( j > r ){
     // 如果右半部分元素已经全部处理完毕            arr[k] = aux[i-l]; i ++;        }        else if( aux[i-l] < aux[j-l] ) {
     // 左半部分所指元素 < 右半部分所指元素            arr[k] = aux[i-l]; i ++;        }        else{
     // 左半部分所指元素 >= 右半部分所指元素            arr[k] = aux[j-l]; j ++;        }    }}// 递归使用归并排序,对arr[l...r]的范围进行排序void _mergeSort(int arr[], int l, int r){
       if( l >= r )        return;    int mid = (l+r)/2;    _mergeSort(arr, l, mid);     _mergeSort(arr, mid+1, r);     _merge(arr, l, mid, r);}void mergeSort(int arr[], int n){
       _mergeSort( arr , 0 , n-1 );}//打印void printLn(int arr[],int n){
          for(int i=0;i
   

7.基数排序

图片来源

1.首先看最大位为多少位，例如最大位1100，则有4位。2.依次遍历所有数据的个位，十位，百位等进行入“桶”(桶是指1~9)。当遇到有的元素是2位，有的元素是3位时，可以把十位的数据的前面补0例如：10 100这些数据，我们可以看成010 100进入依次入“桶”。

代码：

#include 
   
    using namespace std;int Max_bit(int arr[],int n){
       int maxSize=arr[0];    for(int i=0;i