排序算法（1）

目次​
1.直接插入排序
代码实现
时间复杂度 
2. 冒泡排序
代码实现
时间复杂度
3. 对比直接插入排序和冒泡排序
4. 希尔排序
​
代码实现 （2种版本）
特性总结
5. 选择排序
代码实现（2种版本）
时间复杂度

---

1.直接插入排序

   基本头脑：
  把第一个元素看成有序，把第二个元素插入进去，前两个元素有序，把第三个元素插入进去，前三个元素已经有序，把第四个元素插入进去，以此类推，这样从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的得当位置。得到一个新的有序序列。现实中我们玩扑克牌时，就用了插入排序的头脑。
    它的工作原理为将待分列元素划分为【已排序】和【未排序】两部分，每次从【未排序】元素中选择一个插入到【已排序】元素中的正确位置。
  动图： 

代码实现

1. //插入排序
2. void InsertSort(int* a, int n)  //n个数据
3. {
4.         for (int i = 0; i < n - 1; i++) //最后end=n-2，注意i的取值范围
5.         {
6.                 int end = i;                 
7.                 int tmp = a[end + 1];
8.                 //[0,end]有序，把end+1位置的值插入到这个区间中，保持有序
9.                 while (end >= 0)
10.                 {
11.                         if (tmp < a[end])
12.                         {
13.                                 a[end + 1] = a[end]; //数据往后挪
14.                                 --end;
15.                         }
16.                         else
17.                         {
18.                                 break;
19.                         }
20.                 }
22.                 a[end + 1] = tmp; //这条语句没有放到上面的else语句里是为了兼容end=-1的情况，所有值都比tmp值大，把它放在a[0]处
23.         }
24. }

复制代码

时间复杂度 

   最好环境：要排序的数据自己就有序，没有移动，统共比较了n-1次，时间复杂度为O(n)
  最坏环境：即待排数据是逆序的，必要比较1+2+3+……+n-1=(n-1)(1+n-1)/2次，时间复杂度O(n²)
  总的时间复杂度为O(n²)。
    1. 元素聚集越接近有序，直接插入排序算法的时间服从越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳固性：稳固
  2. 冒泡排序

代码实现

1. void BubbleSort(int* a, int n)
2. {
3.         for (int j = 0; j < n-1; j++)
4.         {
5.                 int flag = 0;//若flag为1，则有数据交换，否则退出循环
6.                 //单趟
7.                 for (int i = 0; i < n-j; i++)
8.                 {
9.                         if (a[i - 1] > a[i])
10.                         {
11.                                 Swap(&a[i - 1], &a[i]);
12.                                 flag = 1;
13.                         }                       
14.                 }
16.                 if (flag == 0)
17.                 {
18.                         break;
19.                 }
20.         }       
21. }

复制代码

时间复杂度

   最好环境，待排序的数据有序，统共进行n-1次比较，没有数据交换，时间复杂度为O(n)。
  最坏环境：待排序数据是逆序的，必要进行n-1+n-2+……+3+2+1=(n-1)(n-1+1)/2次比较。
  总的时间复杂度为O(n²)。
  3. 对比直接插入排序和冒泡排序

   虽然它们的时间复杂度都为O(n²)，但是插入排序在多数环境下会优于冒泡排序。假如数据存在大量重复元素或已经部分有序，插入排序通常会比冒泡排序更快，由于插入排序可以利用这些特点来淘汰比较和移动的次数，对于完全随机分布的数据聚集，两者的性能相差不大。
  4. 希尔排序

   希尔排序是一种排序算法，由美国计算机科学家Donald Shell于1959年提出。希尔排序法又称缩小增量法。
    基本头脑：将待排序的元素分为多个子序列，子序列之间相距某个“增量”，然后对每个子序列进行插入排序。然后徐徐减小增量排序，最终将增量减小到1，此时序列已经基本有序，只需完成最后一轮的插入排序，只进行了少量的比较和交换利用，大大进步了排序服从。
    基本有序：小的数据基本在前面，大的数据基本在反面，不大不小的基本在中央。
    将数据分成几组，增量gap是几就是几组，每个组分别进行插入排序，缩小隔断gap的值，重复上述过程，最后gap=1，进行最后一次插入排序就完成排序了。
  

图解： 

代码实现 （2种版本）

1. //方便理解版本
2. void ShellSort(int* a, int n)
3. {
4.         int gap = n;//将数组的长度赋值给gap，再设置循环使gap除以3得到 分成4组 分成2组 分成1组(依据上图分析)
5.         while (gap > 1)
6.         {
7.                 gap = gap / 3 + 1; //+1为了保证gap最后是1，gap>1是预排序，gap=1是插入排序
8.                
9.                 for (int j = 0; j < gap; j++) //j变量指向初始位置，gap组依次排序，一组一组来！
10.                 {                       
11.                         for (int i = j; i < n - gap; i += gap) //注意控制好i的取值范围，防止越界
12.                         {
13.                                 int end = i;
14.                                 int tmp = a[end + gap];
15.                                 while (end >= 0)
16.                                 {
17.                                         if (tmp < a[end])
18.                                         {
19.                                                 a[end + gap] = a[end];
20.                                                 end -= gap;
21.                                         }
22.                                         else
23.                                         {
24.                                                 break;
25.                                         }
26.                                 }
27.                                 a[end + gap] = tmp;
28.                         }
29.                 }
30.         }       
31. }

复制代码

1. //优化版本，相对于上面减少一层循环，效率无区别
2. void ShellSort(int* a, int n)
3. {
4.         int gap = n;
5.         while (gap > 1)
6.         {
7.                 gap = gap / 3 + 1;
9.                 for (int i = 0; i < n - gap; i++) //多组并着走！
10.                 {
11.                         int end = i;
12.                         int tmp = a[end + gap];
13.                         while (end >= 0)
14.                         {
15.                                 if (tmp < a[end])
16.                                 {
17.                                         a[end + gap] = a[end];
18.                                         end -= gap;
19.                                 }
20.                                 else
21.                                 {
22.                                         break;
23.                                 }
24.                         }
25.                         a[end + gap] = tmp;
26.                 }               
27.         }
28. }

复制代码

特性总结

   １．希尔排序是对直接插入排序的优化。
  ２．当gap > 1时都是预排序，目标是让数组更接近于有序。当gap == 1时，数组已经基本接近有序，只需最后插入排序进行少量的比较和交换利用，这样就会很快。这样整体而言，可以到达优化的效果。
  ３．希尔排序的时间复杂度不好计算，由于gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，有学者经过大量计算，得出结果约莫在Ｏ（n＾1.25） 到 Ｏ（1.6*n²)　范围内，我们临时按照这个来算。
  ４．稳固性：不稳固。
  5. 选择排序

   基本头脑： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
  动图： 

 
   流程：
  

• 在元素聚集 [0,n-1] 中选择最小的数据,将其和第1个位置的数据交换。
  
• 接着从剩下的n-1个数据中选择最小的数，将其和第2个位置的数据交换。
  
• 不断重复上面步调，直到最后两个元素发生交换，完成排序。
  

  代码实现（2种版本）

1. void SelectSort(int* a, int n)    // [0,n-1]
2. {
3.                
4.         for (int i = 0; i < n - 1; i++)
5.         {
6.                 int mini = i;
7.                 for (int j = i + 1; j < n; j++)
8.                 {
9.                         if (a[j] < a[mini])
10.                         {
11.                                 mini = j;
12.                         }                       
13.                 }
14.                 if (mini != i)
15.                 {
16.                         Swap(&a[i], &a[mini]);
17.                 }               
18.         }
19. }

复制代码

1. //优化版本（一次性找出最大的数和最小的数的下标）
2. void SelectSort(int* a, int n)   // [0,n-1]
3. {
4.         int begin = 0, end = n - 1;
5.         while (begin < end)
6.         {
7.                 int mini = begin, maxi = begin;
8.                 for (int i = begin + 1; i <= end; i++)//遍历一遍，同时选出最小的数和最大的数的下标
9.                 {
10.                         if (a[i] > a[maxi])
11.                         {
12.                                 maxi = i;
13.                         }
14.                         if (a[i] < a[mini])
15.                         {
16.                                 mini = i;
17.                         }
18.                 }
19.                 Swap(&a[begin], &a[mini]);
21.                 if (begin == maxi)  //如果某次循环时初始元素下标begin处的值就是最大的数，当把mini处的值赋给begin，begin下标处的值发生改变，变成最小的数，就不能赋值给end了，需要更新一下maxi的值再发生交换
22.                 {
23.                         maxi = mini;
24.                 }
26.                 Swap(&a[end], &a[maxi]);
27.                 begin++;
28.                 end--;
29.         }
30. }

复制代码

时间复杂度

   无论最好还是最坏环境，其比较次数都是一样多的，必要进行n-1+n-2+n-3+……+2+1=(n-1)(n-1+1)/2次比较，对于交换次数而言，最好的时间交换0次，最坏的时间交换n-1次，基于最终的排序时间是比较与交换次数的总和，因此，总的时间复杂度为O(n²)。
    与冒泡排序的时间复杂度相同，但是在性能上要略优于冒泡排序。选择排序是不稳固的排序算法
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。