写在前面
十种常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
算法复杂度：
相关概念：
- 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
- 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。
1、冒泡排序（Bubble Sort）- 交换排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1、算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤 1~3，直到排序完成。
1.2、动图演示
1.3、代码实现
设数组长度为N
- 比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
- 这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就 “沉” 到数组第 N-1 个位置，
- N＝N-1; 如果 N 不为 0，那么重复前面两个步骤，否则排序完成。
第一种实现：
|
1 2 3 4 5 6 7 8 9 10 |
static void BubbleSort(int a[],int n){ int i, j; for (i = 0; i < n; i++) { for (j = 1; j < n-1; j++) { if(a[j-1] >a[j]){ Swap(a, j, j-1); } } } } |
第二种实现：
我们设置一个 flag，如果这一趟发生了交换，则为 true，否则为 false。明显如果有一趟没有发生交换，说明排序已经完成。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static void BubbleSort2(int a[],int n){ int j ,k; boolean flag; k = n; flag = true; while(flag){ flag = false; for (j = 1; j < k; j++) { if (a[j-1] > a[j]) { Swap(a, j, j-1); flag = true; } } k--; } } |
第三种实现：
我们会出现这么一种情况，假设有 100 个数字，只有前 10 个无序，后面的 90 个全部都有序，那么我们就不需要每次都要往后遍历，只需要遍历到需要最后一次交换的位置即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
static void BubbleSort3(int a[],int n){ int j ,k ; int flag; flag = n; while(flag > 0){ k = flag; flag = 0; for (j = 1; j < k; j++) { if(a[j-1] > a[j]){ Swap(a, j, j-1); flag = j; } } } } |
2、快速排序（Quick Sort）- 交换排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2.1、算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.2、动图演示
2.3、代码实现
第一种实现（挖坑填数+分治法）：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public int AdjustArray(int s[],int l,int r){ int i = l,j = r; int x = s[l]; //s[i] 即s[i] 就是一个坑 while(i < j){ while(i < j && s[j] >= x){ j--; } if(i < j){ s[i] = s[j]; i++; } //从左向右找大于或等于x的数来填s[j] while(i < j && s[i] < x){ i++; } if(i < j){ s[j] = s[i]; j--; } } //结束之后 i等于j s[i] = x; return i; } void quick_sort01(int s[],int l,int r){ if(l < r){ int i = AdjustArray(s, l, r); quick_sort01(s, l, i-1); quick_sort01(s, i+1, r); } } |
第二种，代码改进：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
void quickSort(int s[],int l,int r){ if(l < r){ int i = l;int j = r; int x = s[l]; while(i < j){ while(i < j && x <= s[j]){ //从右向左找第一个小于x的数 j--; } if(i < j){ s[i++] = s[j]; } while(i < j && x > s[i] ){ //从左向右找第一个大于等于x的数 i++; } if(i < j){ s[j--] = s[i]; } } s[i] = x; quickSort(s, l, i-1);//递归调用 quickSort(s, i+1, r); } } |
3、简单选择排序（Selection Sort）- 选择排序
选择排序 (Selection-sort) 是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
3.1、算法描述
n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为 R [1..n]，有序区为空；
- 第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R [1..i-1] 和 R (i..n）。该趟排序从当前无序区中 – 选出关键字最小的记录 R [k]，将它与无序区的第 1 个记录 R 交换，使 R [1..i] 和 R [i+1..n) 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
- n-1 趟结束，数组有序化了。
3.2、动图演示
3.3、代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
static void SelectSort(int a[],int n){ for (int i = 0; i < n; i++) { int key = i; int min = a[i]; for (int j = i; j < n; j++) { if(min > a[j]){ min = a[j]; key = j; } } Swap(a, i, key); } } |
3.4 算法分析
表现最稳定的排序算法之一，因为无论什么数据进去都是 O (n2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
4、堆排序（Heap Sort）- 选择排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
4.1、算法描述
- 将初始待排序关键字序列 (R1,R2….Rn) 构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素 R [1] 与最后一个元素 R [n] 交换，此时得到新的无序区 (R1,R2,……Rn-1) 和新的有序区 (Rn), 且满足 R [1,2…n-1]<=R [n]；
- 由于交换后新的堆顶 R [1] 可能违反堆的性质，因此需要对当前无序区 (R1,R2,……Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，得到新的无序区 (R1,R2….Rn-2) 和新的有序区 (Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。
4.2、动图演示
4.3、代码实现
堆的插入：
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父节点到根节点必然是一个有序的数列，现在的任务就是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据插入到一个有序空间中。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void MinHeapFixup(int a[],int i) { int j, temp; temp = a[i]; j = (i-1)/2; //父节点 while(j >= 0 && i != 0) { if(a[j] < temp) { break; } a[i] = a[j]; //把较大的子结点往下移动，替换它的子节点 i = j; j = (i -1 )/2; } a[j] = temp; } |
堆的删除：
按照定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根节点，然后在从根结点开始进行一次从上向下调整。调整时先在左右子树找到最小的如果父节点比这个最小的子节点还小，说明不需要调整了，反之将父节点和它交换之后再考虑后面的节点。相当于从根节点讲一个数据的下沉的过程。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//从第i个节点开始调整，n为节点的总数，从0开始计算，i节点的子节点为 2*i+2,2*i+2 void MinHeapFixDown(int a[],int i,int n){ int j ,temp; temp = a[i]; j = 2*i+1; while(j < n){ if(j +1 < n && a[j+1] < a[j])//在左右子树中查找最小的 j++; if(a[j] > temp){ break; } a[i] = a[j]; //将较小的子结点往上移动 替换它的父节点 i = j; j = 2 * i +1; } a[i] = temp; } //在最小堆中删除数 void MinHeapDelete(int a[],int n){ Swap(a, 0, n-1); MinHeapFixDown(a, 0, n-1); } |
创建最小堆：
|
1 2 3 4 5 6 |
//建立最小堆 void MakeMinHeap(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) MinHeapFixdown(a, i, n); } |
评论1