相关推荐：
5、简单插入排序（Insertion Sort）- 插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
5.1、算法描述
一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤 2~5。
5.2、动图演示
5.3、代码实现
第一种：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
static void InsertSort1(int a[],int n){ for (int i = 1; i < n; i++) { if(a[i] < a[i-1]){ int j = i -1; int x = a[i]; a[i] = a[i-1]; while(x < a[j]){ a[j+1] = a[j]; j--; } a[j+1] = x; } } } |
第二种：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
static void InsertSort2(int a[],int n){ for (int i = 1; i < n; i++) { for (int j = i-1; j >= 0 && a[j+1] < a[j] ; j--) { Swap(a,j, j+1); } } } static void Swap(int a[],int j, int k){ int tem = a[j]; a[j] = a[k]; a[k] = tem; } |
5.4、算法分析
插入排序在实现上，通常采用 in-place 排序（即只需用到 O (1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
6、希尔排序（Shell Sort）- 插入排序
1959 年 Shell 发明，第一个突破 O (n2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
基本思想：
先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时候，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下，效率很高。
6.1、算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
6.2、动图演示
6.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 |
static void ShellSort(int a[],int n) { int i , j , gap; for ( gap = n/2; gap > 0; gap/=2) { for (i = 0; i < gap; i++) { for (j = i+gap; j < n; j+=gap) { if (a[j] < a[j - gap]) { int temp = a[j]; int k = j - gap; while(k >= 0 && a[k] > temp){ a[k+gap] = a[k]; k -= gap; } a[k+gap]= temp; } } } } } |
第二种我们进行下改进：
原来每次从 1A 到 1E，从 2A 到 2E，可以改成从 1B 开始，先和 1A 比较，然后取 2B 和 2A 比较，再取 1C 和组内的数据比较。 这种每次从数组第 gap 个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
static void ShellSort2(int a[],int n){ int j , gap; for (gap = n/2; gap > 0; gap/=2) { for (j = gap; j < n; j++) { //从数组的第gap个元素开始 if(a[j] < a[j - gap]){//每个元素与自己组内的数据进行直接插入排序 int temp = a[j]; int k = j - gap; while(k >= 0 && a[k] > temp){ a[k+gap] = a[k]; k -= gap; } a[k + gap] = temp; } } } } |
第三种，我们用 直接排序 的第三种方法:
|
1 2 3 4 5 6 7 8 9 10 |
static void ShellSort3(int a[], int n){ int j , k ,gap; for (gap = n/2; gap < n; gap/=2) { for (j = gap; j < n; j++) { for (k = j-gap; k >= 0 && a[k] > a[k-gap]; k -= gap) { Swap(a, k+gap, k); } } } } |
6.4、算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的。
7、归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 路归并。
7.1、算法描述
- 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
7.2、动图演示
7.3、代码实现
首先考虑下如何将两个有序数列合并，这个非常简单，只要从比较两个数列的第一个数，谁小就取谁，取了之后，就在对应数列中删除这个数，然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static void MergeArray(int a[],int n,int b[],int m,int c[]){ int i ,j , k; i = k = j = 0; while(i < n && j < m){ if(a[i] < b[j]){ c[k++] = a[i++]; }else{ c[k++] = b[j++]; } } while(i < n){ c[k++] = a[i++]; } while(j < m){ c[k++] = a[i++]; } } |
那么我们看出来，合并有序数列的效率是比较高的，可以达到 O（n）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分为二组 A,B, 如果这两组组内的数据是有序的，那么就可以很方便的将这两组的数据进行合并。
|
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 36 37 38 39 40 |
static void mergeArray(int a[], int first,int mid,int last,int temp[]) { int i = first; int j = mid+1; int m = mid; int n = last; int k = 0; while(i <= m && j< n) { if(a[i] < a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } while(i <= m) { temp[k++] = a[i++]; } while(j < n) { temp[k++] = a[i++]; } for (i = 0; i < k; i++) { a[first+i] = temp[i]; } } void mergeSort(int a[],int first,int last,int temp[]){ if(first < last){ int mid = (first+last)/2; mergeSort(a, first, mid, temp);//左边有序 mergeSort(a, mid+1, last, temp);//右边有序 mergeArray(a, first, mid, last, temp);//再将两个有序数列合并 } } |
归并排序的效率是比较高的，设数列长为 N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为 O (N)，故一共为 O (NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在 O (NlogN) 的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
7.4、算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O (nlogn）的时间复杂度。代价是需要额外的内存空间。
评论2