图解法—-十大排序算法汇总—-（总有你需要的那种）好好学习。天天编程-

引言

十大排序算法分别为：

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序，基数排序、桶排序

十种排序算法一共可分为两类。分别是比较排序和非比较排序。

• 比较排序：通过比较各个数的大小来交换各个数顺序，达到排序的效果。
• 非比较排序：不用通过比较，就可以达到排序的效果，平均时间复杂度比比较排序低。

十种排序算法的复杂度

稳定性：比如对期末数学成绩进行排序，假如小明和小红都是95分，在排序前小明在小红的前面，如果排序后，小明仍然在小红的前面，那就说明这个排序算法是稳定的，否则这种排序就是不稳定的。

时间复杂度：排序时，对数据操作的总次数。

空间复杂度：排序时，需要花费的内存空间。

        下面就会对十种排序算法汇总，但是不会展开说，如果对某个算法不太清楚，可以点击下面的链接，在链接里面有详细的讲解 

1. 经典算法（一）—-冒泡排序—-图解法让你快速入门

2. 经典算法（二）—-选择排序—-图解法让你快速入门

3. 经典算法（三）—-插入排序—-图解法让你快速入门

4. 经典算法（四）—-希尔排序—-图解法让你快速入门

5. 经典算法（五）—-归并排序—-图解法让你快速入门

6. 经典算法（六）—-快速排序—-图解法让你快速入门

7. 经典算法（七）—-  堆排序 —-图解法让你快速入门

8. 经典算法（八）—-计数排序—-图解法让你快速入门

9. 经典算法（九）—-基数排序—-图解法让你快速入门

10. 经典算法（十）—-  桶排序  —-图解法让你快速入门

上面的每篇文章都对各种算法有详细得讲解过程，可以 哪里不会点哪里！！！

一、冒泡排序

冒泡排序是一种简单的排序算法，它的实现过程就是每遍历一遍，把最大的数放到最后面，直到排序完成为止

算法描述：

1. 从头到尾遍历要排序的数，每次比较相邻的两个数，如果第一个比第二个大，就交换位置。
2. 直到遍历结束，这时候最大的数就会被移动到最后，那这个数 就处理完毕了。
3. 除了已经处理好的数，其他的数重复1-2的操作，直到排序完成

动画演示：

代码实现：

 #include<iostream> using namespace std; //冒泡排序函数    稳定  void BubbleSort(int arr[],int len) {  int temp;  for(int i=0;i<len-1;i++)  {   for(int j=0;j<len-i-1;j++)   {    if(arr[j]>arr[j+1])    {     temp=arr[j];     arr[j]=arr[j+1];     arr[j+1]=temp;    }   }  } } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度     //排序   BubbleSort(arr,len);    //输出   printf(arr,len);  return 0; }

二、选择排序

选择排序的原理：从未排序的数组中选择出一个最大的放到数组的第一个位置，重复前面的操作，继续从未排序的数中选择最大的，放到第二个位置，直到排序完成。

算法描述：

1. 遍历所未排序的数，找出一个一个最小的数，记录它的数组下标。
2. 拿最小的数和未排序数组的第一个数交换位置。
3. 重复1-2操作，直到排序完成。

动画演示：

代码实现：

 #include<iostream> using namespace std; //选择排序函数    不稳定  void SelectionSort(int arr[],int len) {  int temp;  for(int i=0;i<len-1;i++)  {   int minx=i;   for(int j=i+1;j<len;j++)   {    if(arr[j]<arr[minx]) //寻找最小的数      minx=j;         //记录对应的下标    }   temp=arr[i];   arr[i]=arr[minx];   arr[minx]=temp;  } } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度     //排序   SelectionSort(arr,len);    //输出   printf(arr,len);  return 0; }

三、插入排序

插入排序的原理：首先默认要排序的数组第一个元素为有序序列，然后扫描未排序的每个数，把每个数都插入到有序序列中，插入的方法就是从后向前扫描有序序列，找到一个合适的位置，使插入后的序列仍然是有序序列。

算法描述：

1. 默认第一个数为有序序列，开始遍历未排序的每一个数。
2. 当遍历到某个数时，首先拿一个变量把这个数存取来，再拿这个数和有序序列从后向前比较，如果有这个数比有序序列小，且没有有序序列还有数未比较，那就把有序序列的数后移（为插入数准备位置）。
3. 重复比较操作，直到找到合适的位置，把要插入的数放进去即可。
4. 遍历未排序的每个数，直到所有的数都插入到有序序列中之后，数组就排序好了。

动画演示：

代码实现：

 #include<iostream> using namespace std; //插入排序函数    稳定  void InsertionSort(int arr[],int len) {  int temp;  for(int i=1;i<len;i++)  {   int index=i-1;//前i-1个数已经排序好了   int current=arr[i];   while(index>=0&&arr[index]>current)   {    arr[index+1]=arr[index];     index--;    }   arr[index+1]=current;  } } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度     //排序   InsertionSort(arr,len);    //输出   printf(arr,len);  return 0; }

四、希尔排序

希尔排序就是插入排序的改进版，在希尔排序中引入一个 “增量”，实现了分组插入排序的过程，首先把各自分组用插入排序实现有序，再实现数组的整体有序。

算法描述：

1. 定义增量，确定增量的变化过程（最后增量一定要变成1）。
2. 对于每个增量，都用一边插入排序，实现各自分组的有序。
3. 最后一增量为1时，再用一遍插入排序，就是实现了整理有序。

代码实现：

 #include<iostream> using namespace std; //希尔排序函数    不稳定  void ShellSort(int arr[],int len) {  //increment是增量   int increment=len;  do{   increment=increment/3+1;   for(int i=increment;i<len;i++)   {    int current=arr[i];    int index=i-increment;    while(index>=0&&arr[index]>current)    {     arr[index+increment]=arr[index];     index-=increment;    }    arr[index+increment]=current;   }     } while(increment>1); } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {   //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度   //排序   ShellSort(arr,len);  //输出   printf(arr,len);       return 0; }

五、归并排序

        归并排序的过程一共分两大步，第一步：分，把一个大数组分成一个个小数组；第二步：合，从一个个的小数组，合成大数组，在合的过程中，按照大小顺序进行合成，合成的大数组就是有序的，这样就达到了排序的效果。

算法描述：

1. 利用分治法，把数组实现分的操作。
2. 再写一个实现数组合并的函数，合成之后，数组实现了有序。

动画演示：

代码实现：

 #include<iostream> using namespace std;  //将两个有序数列arr[first...mid]和arr[mid...last]合并 void MergeArray(int arr[],int first,int mid,int last,int temp[]) {  int i=first, j=mid+1;  int m=mid  , n=last;  int k=0;    while(i<=m&&j<=n)  {   if(arr[i]<=arr[j])    temp[k++]=arr[i++];   else    temp[k++]=arr[j++];  }    while(i<=m)   temp[k++]=arr[i++];     while(j<=n)   temp[k++]=arr[j++];     for(i=0;i<k;i++)   arr[first+i]=temp[i]; }    //归并排序函数    稳定  void MergeSort(int arr[],int first,int last,int temp[]) {  if(first<last)  {   int mid=(first+last)/2;   MergeSort(arr,first,mid,temp);   MergeSort(arr,mid+1,last,temp);   MergeArray(arr,first,mid,last,temp);  } } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";   cout<<endl; } int main() {  //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度   int temp[9];  //排序   MergeSort(arr,0,len-1,temp);    //输出   printf(arr,len);  return 0; }

六、快速排序

        快速排序的原理就是首先定一个 “基准数”，再把基准数移动到合适的位置，这个位置要满足他前面位置的数都比基准数小，它后面位置的数，都比基准数大。

算法描述：

1. 首先定一个基准数，在设置两个哨兵，这两个哨兵分别从后面往前走、从前面往后走。
2. 如果后面的哨兵找到了比基准数小的数，那就停下。
3. 如果前面的哨兵找到了比基准数大的数，那就停下。
4. 交换这两个哨兵位置的数。然后这两个哨兵再按照自己先前的方向继续走。
5. 通过上面几步，就把基准数移动到了合适的位置，然后在利用分治的思想，以基准数为分界线，把数组分为两部分，这两部分都执行上面的操作。直到数组有序位置。

动画演示：

代码实现：

 #include<iostream> using namespace std; //快速排序函数    不稳定  void QuickSort(int arr[],int first,int last) {  if(first>last)//控制递归结束    return ;  int i=first,j=last;  int temp=arr[first];//基准数  while(i!=j)//i和j不碰头   {   //顺序很重要，要先从右往左找    while(arr[j]>=temp&&i<j)     j--;   //上面循环结束的条件有两种，   //一是查到了比基准数小的，   //二是 i与j碰头了   while(arr[i]<=temp && i<j)    i++;    //循环结束条件同上      //下面交换两个数在数组中的位置   if(i!=j) //两个循环结束的条件都不是i和j碰头   {    int t=arr[i];    arr[i]=arr[j];    arr[j]=t;   }   }   //最终一定会碰头，交换基准数和碰头那个位置的数   arr[first]=arr[i];  arr[i]=temp;       QuickSort(arr,first,i-1);//分的前一部分   QuickSort(arr,i+1,last); //分的后一部分  } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={5,8,6,2,7,1,9,3,4};  int len=9;//要排序的数组长度     //排序   QuickSort(arr,0,len-1);    //输出   printf(arr,len);  return 0; }

七、堆排序

        堆排序的算法实现过程就是利用了大顶堆或者小顶堆，比如要从小到大排序，那就先把未排序的数组转换成大顶堆，然后把最大的数放到调到数组尾部，重复前面的操作即可。

算法描述：

1. 首先堆化数组，把要排序的数转换成大顶堆。
2. 把大顶堆中堆顶数据移动到数组尾部，然后在堆化数组。
3. 重复第二步的操作，知道所有的数据都排序完成。

代码实现：

 #include<iostream> using namespace std; //堆排序函数    稳定   void HeapAdjust(int arr[],int first,int last) {  int temp=arr[first];//暂存“根”结点   int j;//子结点   for(j=2*first;j<=last;j=j*2)  {   //下面if语句的作用是找出子结点中比较大的那个    //j是左节点，j+1是右节点，   //如果右节点大，那j+1就可以了，如果左节点大那就不用+1   //执行完下面的语句，j下标是较大的那个子结点的下标    if(j<last &&arr[j]<arr[j+1])    j++;      //下面if语句的作用是如果“根”结点大于子结点，   //结束查找即可   if(temp>arr[j])    break;       //理解下面两条语句可以类比插入排序，   //还记得插入排序中的元素后移吗？ 这里是“下移”    arr[first]=arr[j];   first=j; //如果下移，记录对应的下标，方便下次下移   }  //同样类比插入排序，把要插入的元素，放到合适的位置   arr[first]=temp;  }   void HeapSort(int arr[],int len)  {  for(int i=len/2;i>0;i--)  {   HeapAdjust(arr,i,len);  }  for(int i=len;i>0;i--)//需要交换几次位置的次数   {   //下面三行的代码是把堆顶最大的元素和堆尾最后一个元素换位置   //这样一来，最大元素就在数组尾部了，   //因此大顶堆 是用来从小 到大排序的    int temp=arr[1];   arr[1]=arr[i];   arr[i]=temp;      //对堆剩下的元素继续排序。    HeapAdjust(arr,1,i-1);  } }  //输出数组的值 void printf(int arr[],int len) {  for(int i=1;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组 ,为了方便理解，数组下标从1开始   int arr[]={0,5,8,6,2,7,1,9,3,4};  int len=10;//要排序的数组长度     //排序   HeapSort(arr,len-1);    //输出   printf(arr,len);  return 0; }

八、计数排序

        计数排序的思想就是统计每个数的出现的次数，然后再根据统计的次数，输出每个数。

算法思想：

1. 首先找出要排序数组的最大值和最小值。
2. 根据最大值和最小值确定统计数组的长度。
3. 遍历一遍，统计出来每个数出现的次数。
4. 按照统计数组，输出每个数。

动画演示：

代码实现：

 #include<iostream> using namespace std; //计数排序函数    稳定  void CountingSort(int arr[],int len) {  int minx=99999,maxn=-99999;  //下面for循环是求出来要排序数组的最大值和最小值   for(int i=0;i<len;i++)  {   if(arr[i]>maxn)    maxn=arr[i];   if(arr[i]<=minx)    minx=arr[i];  }  //cout<<maxn<<" "<<minx<<endl;    int l=maxn-minx+1;//变量 l 是要开辟数组的长度   int count[l]={0};    //下面的代码是统计作用，不过统计时要减去数组最小值，方便存储   for(int i=0;i<len;i++)   count[arr[i]-minx]++;    //累加   for(int i=0;i<l;i++)  {   count[i]+=count[i-1];  }    int temp[len]={0};//用来排序好的数组      for(int i=len-1;i>=0;i--)//逆序遍历。   {   int ans=arr[i]-minx;   temp[--count[ans]]=arr[i];//先减减的原因是数组下标从0开始的  }  //经过上面的逆序遍历，现在temp数组就是排序好的成绩数组     //把排序好的数组放到arr数组中 ，方便后面的打印   for(int i=0;i<len;i++)   arr[i]=temp[i]; } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={1,5,4,2,2,3,1,1,3,1,5};  int len=11;//要排序的数组长度     //排序   CountingSort(arr,len);    //输出   printf(arr,len);  return 0; }

九、基数排序

        基数排序的原理就是按位进行排序，比如从低位到高位，首先先个位，再十位百位，直到达到最高位。每一次的排序都是按计数排序来实现的

算法描述：

1. 首先求出要排序数的最大值一共有几位，根据这个决定排序的次数。
2. 每位排序是都是用计数排序实现的

动画描述：

代码实现：

 #include<iostream> using namespace std;  //统计数组中 最大数的位数  int max(int arr[],int len) {  int maxn=0;  for(int i=0;i<len;i++)  {   int count=0,data=arr[i];   while(data)   {    count++;    data/=10;   }   if(count>maxn)    maxn=count;  }  return maxn; }   //基数排序函数    稳定  void RadixSort(int arr[],int len) {  int maxn=max(arr,len);//首先求出最大位数  int num=1;//求位数用   for(int k=0;k<maxn;k++)//根据位数，判断遍历几次   {   int count[10]={0};   for(int i=0;i<len;i++)//把数据放入桶内    {    int ans=arr[i]/num%10;    count[ans]++;   }      //下面的过程都是计数排序的过程。   //根据计数排序，把桶内数据排序即可    for(int i=1;i<10;i++)//累加    {    count[i]=count[i]+count[i-1];   }      int temp[len]={0};//用来存放排序后的结果    for(int i=len-1;i>=0;i--)//逆序遍历，保证稳定性    {    int ans=arr[i]/num%10;    temp[count[ans]-1]=arr[i];     count[ans]--;     }       for(int i=0;i<len;i++)    arr[i]=temp[i];       num*=10;//求更高位   }    } //输出数组的值 void printf(int arr[],int len) {  for(int i=0;i<len;i++)   cout<<arr[i]<<" ";  cout<<endl; } int main() {  //要排序的数组   int arr[]={321,563,454,219,541,632,225,678,59,356};  int len=10;//要排序的数组长度     //排序   RadixSort(arr,len);    //输出   printf(arr,len);  return 0; }

十、桶排序

        桶排序的思想就是首先定义几个桶，再把数据放到桶内，然后再把每个桶都排序，最后按照顺序输出。桶排序不太常用

算法描述：

1. 设计好有几个桶，每个桶的范围都为多少
2. 对每个桶进行排序
3. 按照顺序，把每个桶的数据都取出来

桶排序不常用的原因：

1. 每个桶如果用数组存数据，那如果数组不够用怎么办？，因为一组数可能有的很集中，有的很分散，如果数组开大了，那分散的数，就会造成空间浪费。
2. 如果每个桶用链表存，那就不用提前开辟空间了，但是又存在了时间问题，因为如果对链表进行排序，只能进行一遍一遍的遍历（访问链表的数据不能随机访问），那时间复杂度就特别大了。
3. 如果一个要排序的数据特别集中，比如有1000个数据，结果超过了800个数据在一个桶内，那桶排序的优势更体现不出来了。
    

本文的参考和引用：https://www.cnblogs.com/onepixel/articles/7674659.html

 

这篇文章到这就结束了，当然算法排序永远不会结束，各种算法还有各种优化的版本，这里就不写了。

创作不易（尤其是动画的制作），如果本文对你起到了一些帮助，何不点个赞再走呢！！！