插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
一般来说,插入排序都采用 in-place 在数组上实现。具体算法描述如下:
简单插入排序
Shell
static void InsertSort1(int a[],int n){ for (int i = 1; i < n; i++) { if(ai < ai-1){ int j = i -1; int x = ai; ai = ai-1; while(x < aj){ aj+1 = aj; j--; } aj+1 = x; } } }
123456789101112131415 | static void InsertSort1(int a[],int n){ for (int i = 1; i < n; i++) { if(ai < ai-1){ int j = i -1; int x = ai; ai = ai-1; while(x < aj){ aj+1 = aj; j--; } aj+1 = x; } }} |
---|
Shell
static void InsertSort2(int a[],int n){ for (int i = 1; i < n; i++) { for (int j = i-1; j >= 0 && aj+1 < aj ; j--) { Swap(a,j, j+1); } } } static void Swap(int a[],int j, int k){ int tem = aj; aj = ak; ak = tem; }
12345678910111213 | static void InsertSort2(int a[],int n){ for (int i = 1; i < n; i++) { for (int j = i-1; j >= 0 && aj+1 < aj ; j--) { Swap(a,j, j+1); } }} static void Swap(int a[],int j, int k){ int tem = aj; aj = ak; ak = tem;} |
---|
5.4、算法分析
插入排序在实现上,通常采用 in-place 排序(即只需用到 O (1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
1959 年 Shell 发明,第一个突破 O (n2) 的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
基本思想:
先将整个待排序元素序列分割成若干个子序列(由相隔某个“增量”的元素组成)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时候,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下,效率很高。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
Shell
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 (aj < aj - gap) { int temp = aj; int k = j - gap; while(k >= 0 && ak > temp){ ak+gap = ak; k -= gap; } ak+gap= temp; } } } } }
123456789101112131415161718192021222324 | 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 (aj < aj - gap) { int temp = aj; int k = j - gap; while(k >= 0 && ak > temp){ ak+gap = ak; k -= gap; } ak+gap= temp; } } } }} |
---|
原来每次从 1A 到 1E,从 2A 到 2E,可以改成从 1B 开始,先和 1A 比较,然后取 2B 和 2A 比较,再取 1C 和组内的数据比较。 这种每次从数组第 gap 个元素开始,每个元素与自己组内的数据进行直接插入排序显然也是正确的。
Shell
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(aj < aj - gap){//每个元素与自己组内的数据进行直接插入排序 int temp = aj; int k = j - gap; while(k >= 0 && ak > temp){ ak+gap = ak; k -= gap; } ak + gap = temp; } } } }
1234567891011121314151617 | 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(aj < aj - gap){//每个元素与自己组内的数据进行直接插入排序 int temp = aj; int k = j - gap; while(k >= 0 && ak > temp){ ak+gap = ak; k -= gap; } ak + gap = temp; } } }} |
---|
第三种,我们用 直接排序 的第三种方法:
Shell
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 && ak > ak-gap; k -= gap) { Swap(a, k+gap, k); } } } }
12345678910 | 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 && ak > ak-gap; k -= gap) { Swap(a, k+gap, k); } } }} |
---|
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第 4 版)》的合著者 Robert Sedgewick 提出的。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为 2 路归并。
首先考虑下如何将两个有序数列合并,这个非常简单,只要从比较两个数列的第一个数,谁小就取谁,取了之后,就在对应数列中删除这个数,然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出。
Shell
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(ai < bj){ ck++ = ai++; }else{ ck++ = bj++; } } while(i < n){ ck++ = ai++; } while(j < m){ ck++ = ai++; } }
12345678910111213141516171819 | 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(ai < bj){ ck++ = ai++; }else{ ck++ = bj++; } } while(i < n){ ck++ = ai++; } while(j < m){ ck++ = ai++; }} |
---|
那么我们看出来,合并有序数列的效率是比较高的,可以达到 O(n)解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分为二组 A,B, 如果这两组组内的数据是有序的,那么就可以很方便的将这两组的数据进行合并。
Shell
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(ai < aj){ tempk++ = ai++; }else{ tempk++ = aj++; } } while(i <= m) { tempk++ = ai++; } while(j < n) { tempk++ = ai++; } for (i = 0; i < k; i++) { afirst+i = tempi; } } 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);//再将两个有序数列合并 } }
12345678910111213141516171819202122232425262728293031323334353637383940 | 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(ai < aj){ tempk++ = ai++; }else{ tempk++ = aj++; } } while(i <= m) { tempk++ = ai++; } while(j < n) { tempk++ = ai++; } for (i = 0; i < k; i++) { afirst+i = tempi; }} 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) 的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。
归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O (nlogn)的时间复杂度。代价是需要额外的内存空间。