我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

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

　　　　一种是比较排序，时间复杂度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. // 稳定性 ------------ 稳定
   
8. 
   
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. }
    
15. 
    
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.选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。代码如下：

1. 
   
2. 
   
3. // 分类 -------------- 内部比较排序
   
4. // 数据结构 ---------- 数组
   
5. // 最差时间复杂度 ---- O(n^2)
   
6. // 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
   
7. // 平均时间复杂度 ---- O(n^2)
   
8. // 所需辅助空间 ------ O(1)
   
9. // 稳定性 ------------ 稳定
   
10. 
    
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. }
    
17. 
    
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.插入排序的改进：二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目，我们称为二分插入排序，代码如下：

1. 
   
2. 
   
3. // 分类 -------------- 内部比较排序
   
4. // 数据结构 ---------- 数组
   
5. // 最差时间复杂度 ---- O(n^2)
   
6. // 最优时间复杂度 ---- O(nlogn)
   
7. // 平均时间复杂度 ---- O(n^2)
   
8. // 所需辅助空间 ------ O(1)
   
9. // 稳定性 ------------ 稳定
   
10. 
    
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较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列

　我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

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

　　　　一种是比较排序，时间复杂度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. // 稳定性 ------------ 稳定
   
8. 
   
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. }
    
15. 
    
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.选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。代码如下：

1. 
   
2. 
   
3. // 分类 -------------- 内部比较排序
   
4. // 数据结构 ---------- 数组
   
5. // 最差时间复杂度 ---- O(n^2)
   
6. // 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
   
7. // 平均时间复杂度 ---- O(n^2)
   
8. // 所需辅助空间 ------ O(1)
   
9. // 稳定性 ------------ 稳定
   
10. 
    
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. }
    
17. 
    
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.插入排序的改进：二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目，我们称为二分插入排序，代码如下：

1. 
   
2. 
   
3. // 分类 -------------- 内部比较排序
   
4. // 数据结构 ---------- 数组
   
5. // 最差时间复杂度 ---- O(n^2)
   
6. // 最优时间复杂度 ---- O(nlogn)
   
7. // 平均时间复杂度 ---- O(n^2)
   
8. // 所需辅助空间 ------ O(1)
   
9. // 稳定性 ------------ 稳定
   
10. 
    
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较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列