黑马程序员技术交流社区

标题: 常见排序法总结（一）） [打印本页]
作者: wangyupeng123    时间: 2017-7-12 22:47
标题: 常见排序法总结（一））
　我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

　　排序算法大体可分为两种：

　　　　一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

　　　　另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

　1.冒泡排序算法的运作如下：

    比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
    对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    针对所有的元素重复以上的步骤，除了最后一个。
    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

　　由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。冒泡排序的代码如下：
  1. // 分类 -------------- 内部比较排序
  2. // 数据结构 ---------- 数组
  3. // 最差时间复杂度 ---- O(n^2)
  4. // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
  5. // 平均时间复杂度 ---- O(n^2)
  6. // 所需辅助空间 ------ O(1)
  7. // 稳定性 ------------ 稳定

  9. void exchange(int A[], int i, int j)        // 交换A[i]和A[j]
  10. {
  11.     int temp = A[i];
  12.     A[i] = A[j];
  13.     A[j] = temp;
  14. }

  16. int main()
  17. {
  18.     int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大冒泡排序
  19.     int n = sizeof(A) / sizeof(int);               
  20.     for (int j = 0; j < n - 1; j++)            // 每次最大元素就像气泡一样"浮"到数组的最后
  21.     {
  22.         for (int i = 0; i < n - 1 - j; i++)    // 依次比较相邻的两个元素,使较大的那个向后移
  23.         {
  24.             if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
  25.             {
  26.                 exchange(A, i, i + 1);        
  27.             }
  28.         }
  29.     }
  30.     printf("冒泡排序结果：");
  31.     for (int i = 0; i < n; i++)
  32.     {
  33.         printf("%d ", A[i]);
  34.     }
  35.     printf("\n");
  36.     return 0;
  37. }
复制代码

2.选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。代码如下：


  3. // 分类 -------------- 内部比较排序
  4. // 数据结构 ---------- 数组
  5. // 最差时间复杂度 ---- O(n^2)
  6. // 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
  7. // 平均时间复杂度 ---- O(n^2)
  8. // 所需辅助空间 ------ O(1)
  9. // 稳定性 ------------ 稳定

  11. void exchange(int A[], int i, int j)        // 交换A[i]和A[j]
  12. {
  13.     int temp = A[i];
  14.     A[i] = A[j];
  15.     A[j] = temp;
  16. }

  18. int main()
  19. {
  20.     int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };   // 从小到大定向冒泡排序
  21.     int n = sizeof(A) / sizeof(int);               
  22.     int left = 0;                           // 初始化边界
  23.     int right = n - 1;
  24.     while (left < right)
  25.     {
  26.         for (int i = left; i < right; i++)  // 前半轮,将最大元素放到后面
  27.             if (A[i] > A[i + 1])
  28.             {
  29.                 exchange(A, i, i + 1);
  30.             }
  31.         right--;
  32.         for (int i = right; i > left; i--)  // 后半轮,将最小元素放到前面
  33.             if (A[i - 1] > A[i])
  34.             {
  35.                 exchange(A, i - 1, i);
  36.             }
  37.         left++;
  38.     }
  39.     printf("鸡尾酒排序结果：");
  40.     for (int i = 0; i < n; i++)
  41.     {
  42.         printf("%d ", A[i]);
  43.     }
  44.     printf("\n");
  45.     return 0;
  46. }
复制代码

3.插入排序的改进：二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目，我们称为二分插入排序，代码如下：



  3. // 分类 -------------- 内部比较排序
  4. // 数据结构 ---------- 数组
  5. // 最差时间复杂度 ---- O(n^2)
  6. // 最优时间复杂度 ---- O(nlogn)
  7. // 平均时间复杂度 ---- O(n^2)
  8. // 所需辅助空间 ------ O(1)
  9. // 稳定性 ------------ 稳定

  11. int main()
  12. {
  13.     int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序
  14.     int n = sizeof(A) / sizeof(int);
  15.     int i, j, get, left, right, middle;
  16.    
  17.     for (i = 1; i < n; i++)                 // 类似抓扑克牌排序
  18.     {
  19.         get = A[i];                         // 右手抓到一张扑克牌
  20.         left = 0;                           // 拿在左手上的牌总是排序好的,所以可以用二分法
  21.         right = i - 1;                      // 手牌左右边界进行初始化
  22.         while (left <= right)               // 采用二分法定位新牌的位置
  23.         {
  24.             middle = (left + right) / 2;
  25.             if (A[middle] > get)
  26.                 right = middle - 1;
  27.             else
  28.                 left = middle + 1;
  29.         }
  30.         for (j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
  31.         {
  32.             A[j + 1] = A[j];            
  33.         }
  34.         A[left] = get;                    // 将抓到的牌插入手牌
  35.     }
  36.     printf("二分插入排序结果：");
  37.     for (i = 0; i < n; i++)
  38.     {
  39.         printf("%d ", A[i]);
  40.     }
  41.     printf("\n");
  42.     return 0;
  43. }
复制代码

当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2