大话排序--插入排序和希尔排序
排序介绍
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
排序就是将杂乱无章的数据，通过一定的方式将数据按特定的规则顺序排列的过程。
关于排序的算法有很多，这里介绍插入排序和插入排序的升级版——希尔排序。
在介绍排序前先给出构建待排序数组的算法和检测数组是否排好序的算法。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define ALL 50 6 7 /* 用于生成一个随机序列。 */ 8 int *mkArr() 9 { 10 static int arr[ALL]; 11 srand(time(NULL)); 12 13 int i; 14 for (i = 0; i < ALL; i++) 15 { 16 arr[i] = rand()%(ALL*5) + 1; 17 } 18 19 return arr; 20 } 21 22 /* 检测序列是否是从小到大排好序，排好序返回1，否则返回0. */ 23 int checkSort(int arr[]) 24 { 25 int checked = 1; 26 int i; 27 28 /* 检测序列中是否存在一个数比它的后面一个数大 */ 29 for (i = 0; i < ALL - 1; i++) 30 { 31 if (arr[i] > arr[i + 1]) 32 { 33 checked = 0; 34 break; 35 } 36 } 37 38 if (checked) 39 printf("序列已经排好序。\n"); 40 else 41 printf("序列没有排好序。\n"); 42 43 return checked; 44 }
C语言构建随机数组和检测数组是否排好序
1 import java.util.Arrays; 2 import java.util.Random; 3 4 public class Sort { 5 6 /** 7 * 产生一个有n个元素的随机序列并返回该序列。 8 * @param n 序列的元素个数。 9 * @return 返回一个有n个元素的序列。 10 */ 11 public static int[] mkArr(int n){ 12 int[] arr = new int[n]; 13 Random r = new Random(); 14 for (int i = 0; i < n; i++) 15 arr[i] = r.nextInt(n*5)+1; 16 17 return arr; 18 } 19 20 /** 21 * 检测序列是否是从小到大排序的序列。 22 * @param arr 需要进行检测的序列。 23 * @return 如果是从小到大的序列则返回true，否则返回false。 24 */ 25 public static boolean checkSort(int[] arr){ 26 boolean checked = true; 27 for (int i = 0; i < arr.length-1; i++){ 28 if (arr[i] > arr[i+1]){ 29 checked = false; 30 break; 31 } 32 } 33 if (checked) 34 System.out.println("序列已经排好序"); 35 else 36 System.out.println("序列没有排好序"); 37 38 return checked; 39 } 40 }
Java生成随机数组和检测数组是否排好序
1 def mkArr(n=10): 2 '''产生一个有n个数据的随机序列，并返回该序列''' 3 ret = [] 4 for i in range(n): 5 ret.append(random.randint(1, n*5+1)) 6 return ret 7 8 def checkSort(arr): 9 '''检测序列是否是一个从小到大排序的序列''' 10 checked = True 11 for i in range(0,len(arr)-1): 12 #检测序列中是否存在一个数比它后面那个数大 13 if (arr[i] > arr[i+1]): 14 checked = False 15 break 16 if checked: 17 print("序列已经排好序。") 18 else: 19 print("序列没有排好序。") 20 return checked
Python生成随机数组和检测数组是否排好序
插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
已知一个由n个元素组成的无序序列a = { a[0], a[1], a[2], . . . , a[n-1] }，先需要将a按插入排序的规则从小到大排列。
第一步：取一个元素a[0]，此时a[0]是一个只有一个元素的有序序列，a[1], a[2], . . . , a[n-1] 为无序的序列；
第二步：取a[0]的下一个元素a[1]与a[0]进行比较，如果a[1]小于a[0]，a[1]插到a[0]前面，a[0]向后移一位。此时a[0], a[1]组成一个有序的序列， a[2], a[3], . . . , a[n-1] 为无序的序列；
第三步：取a[1]的下一个元素a[2]与a[1]进行比较，如果a[2]小于a[1]，再与a[0]比较，如果小于a[0]则a[2]插到a[0]前面，a[0], a[1]向后移一位；如果不小于a[0]则a[2]插到a[1]前面，a[1]向后移一位。a[0], a[1], a[2]组成一个有序的序列， a[3], a[4], . . . , a[n-1] 是无序的序列；
第四步：重复第三步；直到所有元素排好序。
1 /* 对序列进行插入排序 */ 2 void insertSort(int arr[]) 3 { 4 int i, j; 5 int temp; //用于交换数据的临时变量 6 7 for (i = 1; i < ALL; i++) 8 { 9 for (j = i; j > 0; j--) 10 { 11 if (arr[j] < arr[j-1]) 12 { 13 temp = arr[j]; 14 arr[j] = arr[j-1]; 15 arr[j-1] = temp; 16 }else 17 break; 18 } 19 } 20 }
C语言插入排序
1 public class Sort { 2 3 /** 4 * 对序列进行插入排序。 5 * @param arr 需要进行排序的序列。 6 */ 7 public static void insertSort(int[] arr){ 8 // int count = 0; //用于统计排序过程中进行了多少次数据交换 9 // int loop = 0; //用于统计排序过程进行了多少次循环 10 int temp = 0; //用于数据交换的临时变量 11 12 /* 开始插入排序 */ 13 for (int i = 0; i < arr.length; i++){ 14 // loop++; 15 for (int j = i; j > 0; j--){ 16 // loop++; 17 if (arr[j] < arr[j-1]){ 18 temp = arr[j]; 19 arr[j] = arr[j-1]; 20 arr[j-1] = temp; 21 // count++; 22 } 23 } 24 } 25 // System.out.println("插入排序进行了"+loop+"次循环"+count+"次数据交换"); 26 } 27 28 }
Java插入排序
1 def insertSort(arr): 2 '''对传入的序列进行插入排序 ''' 3 # count = 0 #用于统计排序进行了多少次数据交换次数 4 # loop = 0 #用于统计排序进行了多少次循环 5 for i in range(1, len(arr)): 6 # loop += 1 7 for j in range(i, 0, -1): 8 # loop += 1 9 if (arr[j] < arr[j-1]): 10 arr[j], arr[j-1] = arr[j-1], arr[j] 11 # count += 1 12 else: 13 break 14 # print("插入排序进行了%s循环和%s次数据交换" %(loop, count))
Python插入排序
希尔排序
希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定版本排序算法，因为在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。该方法因D.L.Shell于1959年提出而得名。
希尔排序是基于出入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序是将整个序列分割成若干小的子序列分别进行插入排序。
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。
希尔排序的最后一趟增量为1，也是直接插入排序，但是因为前两趟已将部分数据排好序，最后一趟只有少量数据需要插入排序，而且插入位置也离插入前的位置不远，数据交换次数也变少了。
1 /* 对序列进行希尔排序 */ 2 void shellSort(int arr[]) 3 { 4 int i, j; 5 int temp; //用于交换数据的临时变量 6 int step = ALL/2; //每趟排序的间距 7 8 for (step; step > 0; step /= 2) 9 { 10 for (i = step; i < ALL; i++) 11 { 12 for (j = i - step; j >= 0; j -= step) 13 { 14 if (arr[j] > arr[j + step]) 15 { 16 temp = arr[j]; 17 arr[j] = arr[j + step]; 18 arr[j + step] = temp; 19 }else 20 break; 21 } 22 } 23 } 24 }
C语言希尔排序
1 public class Sort { 2 3 /** 4 * 对序列进行希尔排序。 5 * @param arr 需要进行排序的序列。 6 */ 7 public static void shellSort(int[] arr){ 8 // int count = 0; //用于统计排序过程中进行了多少次数据交换 9 // int loop = 0; //用于统计排序过程进行了多少次循环 10 int temp = 0; //用于数据交换的临时变量 11 12 /* 开始进行希尔排序 */ 13 for (int step = arr.length/2; step > 0; step /= 2){ 14 // loop++; 15 for (int i = step; i < arr.length; i++){ 16 // loop++; 17 for (int j = i - step; j >= 0; j -= step){ 18 // loop++; 19 if (arr[j] > arr[j + step]){ 20 temp = arr[j]; 21 arr[j] = arr[j + step]; 22 arr[j + step] = temp; 23 // count++; 24 }else 25 break; 26 } 27 } 28 } 29 // System.out.println("插入排序进行了"+loop+"次循环"+count+"次数据交换"); 30 } 31 32 }
Java希尔排序
1 def shellSort(arr): 2 '''对传入的序列进行希尔排序 ''' 3 step = len(arr)//2 #设置步长 4 # count = 0 #用于统计排序进行了多少次数据交换次数 5 # loop = 0 #用于统计排序进行了多少次循环 6 while True: 7 # loop += 1 8 for i in range(step, len(arr)): 9 #每趟排序的次数 10 # loop += 1 11 for j in range(i-step, -1, -step): 12 #每趟排序进行的数据比较交换交换 13 # loop += 1 14 if(arr[j] > arr[j+step]): 15 arr[j], arr[j+step] = arr[j+step], arr[j] 16 # count += 1 17 else: 18 break 19 if step == 1: 20 # print("希尔排序进行了%s循环和%s次数据交换" % (loop, count)) 21 break 22 23 step = step//2
Python希尔排序
排序测试代码
1 int main (void) 2 { 3 int *p = mkArr(); 4 int arr[ALL]; 5 int i; 6 /* 打印生成的序列 */ 7 for (i = 0; i < ALL; i++) 8 { 9 arr[i] = *(p + i); 10 printf("%d ", *(p + i)); 11 } 12 printf("\n"); 13 checkSort(arr); 14 15 shellSort(arr); 16 //insertSort(arr); 17 18 /* 打印排序好的序列 */ 19 for (i = 0; i < ALL; i++) 20 { 21 printf("%d ", arr[i]); 22 } 23 printf("\n"); 24 checkSort(arr); 25 26 return 0; 27 }
C语言测试
1 public class Sort { 2 3 public static void main(String[] args) { 4 int[] arr = mkArr(200); 5 checkSort(arr); 6 System.out.println(Arrays.toString(arr)); 7 // insertSort(arr); 8 shellSort(arr); 9 checkSort(arr); 10 System.out.println(Arrays.toString(arr)); 11 } 12 13 }
Java测试
1 ret = mkArr(10) 2 checkSort(ret) 3 print(ret) 4 shellSort(ret) 5 # insertSort(ret) 6 checkSort(ret) 7 print(ret)
Python测试
Java和Python的代码中注释的count和loop是测试排序过程中进行了多少次数据交换和循环的。通过测试，可以很直观的感受到希尔排序的效率要比直接插入排序高很多，排序的数据量越大，越明显。
源代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define ALL 50 6 7 int *mkArr(); 8 9 int checkSort(int arr[]); 10 11 void insertSort(int arr[]); 12 13 void shellSort(int arr[]); 14 15 int main (void) 16 { 17 int *p = mkArr(); 18 int arr[ALL]; 19 int i; 20 /* 打印生成的序列 */ 21 for (i = 0; i < ALL; i++) 22 { 23 arr[i] = *(p + i); 24 printf("%d ", *(p + i)); 25 } 26 printf("\n"); 27 checkSort(arr); 28 29 shellSort(arr); 30 //insertSort(arr); 31 32 /* 打印排序好的序列 */ 33 for (i = 0; i < ALL; i++) 34 { 35 printf("%d ", arr[i]); 36 } 37 printf("\n"); 38 checkSort(arr); 39 40 return 0; 41 } 42 43 /* 用于生成一个随机序列。 */ 44 int *mkArr() 45 { 46 static int arr[ALL]; 47 srand(time(NULL)); 48 49 int i; 50 for (i = 0; i < ALL; i++) 51 { 52 arr[i] = rand()%(ALL*5) + 1; 53 } 54 55 return arr; 56 } 57 58 /* 检测序列是否是从小到大排好序，排好序返回1，否则返回0. */ 59 int checkSort(int arr[]) 60 { 61 int checked = 1; 62 int i; 63 64 /* 检测序列中是否存在一个数比它的后面一个数大 */ 65 for (i = 0; i < ALL - 1; i++) 66 { 67 if (arr[i] > arr[i + 1]) 68 { 69 checked = 0; 70 break; 71 } 72 } 73 74 if (checked) 75 printf("序列已经排好序。\n"); 76 else 77 printf("序列没有排好序。\n"); 78 79 return checked; 80 } 81 82 /* 对序列进行插入排序 */ 83 void insertSort(int arr[]) 84 { 85 int i, j; 86 int temp; //用于交换数据的临时变量 87 88 for (i = 1; i < ALL; i++) 89 { 90 for (j = i; j > 0; j--) 91 { 92 if (arr[j] < arr[j-1]) 93 { 94 temp = arr[j]; 95 arr[j] = arr[j-1]; 96 arr[j-1] = temp; 97 }else 98 break; 99 } 100 } 101 } 102 103 /* 对序列进行希尔排序 */ 104 void shellSort(int arr[]) 105 { 106 int i, j; 107 int temp; //用于交换数据的临时变量 108 int step = ALL/2; //每趟排序的间距 109 110 for (step; step > 0; step /= 2) 111 { 112 for (i = step; i < ALL; i++) 113 { 114 for (j = i - step; j >= 0; j -= step) 115 { 116 if (arr[j] > arr[j + step]) 117 { 118 temp = arr[j]; 119 arr[j] = arr[j + step]; 120 arr[j + step] = temp; 121 }else 122 break; 123 } 124 } 125 } 126 }
C源代码
1 package mySort; 2 3 import java.util.Arrays; 4 import java.util.Random; 5 6 public class Sort { 7 8 /** 9 * 产生一个有n个元素的随机序列并返回该序列。 10 * @param n 序列的元素个数。 11 * @return 返回一个有n个元素的序列。 12 */ 13 public static int[] mkArr(int n){ 14 int[] arr = new int[n]; 15 Random r = new Random(); 16 for (int i = 0; i < n; i++) 17 arr[i] = r.nextInt(n*5)+1; 18 19 return arr; 20 } 21 22 /** 23 * 检测序列是否是从小到大排序的序列。 24 * @param arr 需要进行检测的序列。 25 * @return 如果是从小到大的序列则返回true，否则返回false。 26 */ 27 public static boolean checkSort(int[] arr){ 28 boolean checked = true; 29 for (int i = 0; i < arr.length-1; i++){ 30 if (arr[i] > arr[i+1]){ 31 checked = false; 32 break; 33 } 34 } 35 if (checked) 36 System.out.println("序列已经排好序"); 37 else 38 System.out.println("序列没有排好序"); 39 40 return checked; 41 } 42 43 /** 44 * 对序列进行插入排序。 45 * @param arr 需要进行排序的序列。 46 */ 47 public static void insertSort(int[] arr){ 48 // int count = 0; //用于统计排序过程中进行了多少次数据交换 49 // int loop = 0; //用于统计排序过程进行了多少次循环 50 int temp = 0; //用于数据交换的临时变量 51 52 /* 开始插入排序 */ 53 for (int i = 0; i < arr.length; i++){ 54 // loop++; 55 for (int j = i; j > 0; j--){ 56 // loop++; 57 if (arr[j] < arr[j-1]){ 58 temp = arr[j]; 59 arr[j] = arr[j-1]; 60 arr[j-1] = temp; 61 // count++; 62 } 63 } 64 } 65 // System.out.println("插入排序进行了"+loop+"次循环"+count+"次数据交换"); 66 } 67 68 /** 69 * 对序列进行希尔排序。 70 * @param arr 需要进行排序的序列。 71 */ 72 public static void shellSort(int[] arr){ 73 // int count = 0; //用于统计排序过程中进行了多少次数据交换 74 // int loop = 0; //用于统计排序过程进行了多少次循环 75 int temp = 0; //用于数据交换的临时变量 76 77 /* 开始进行希尔排序 */ 78 for (int step = arr.length/2; step > 0; step /= 2){ 79 // loop++; 80 for (int i = step; i < arr.length; i++){ 81 // loop++; 82 for (int j = i - step; j >= 0; j -= step){ 83 // loop++; 84 if (arr[j] > arr[j + step]){ 85 temp = arr[j]; 86 arr[j] = arr[j + step]; 87 arr[j + step] = temp; 88 // count++; 89 }else 90 break; 91 } 92 } 93 } 94 // System.out.println("插入排序进行了"+loop+"次循环"+count+"次数据交换"); 95 } 96 97 public static void main(String[] args) { 98 int[] arr = mkArr(200); 99 checkSort(arr); 100 System.out.println(Arrays.toString(arr)); 101 // insertSort(arr); 102 shellSort(arr); 103 checkSort(arr); 104 System.out.println(Arrays.toString(arr)); 105 } 106 107 }
Java源代码
1 import random 2 3 def shellSort(arr): 4 '''对传入的序列进行希尔排序 ''' 5 step = len(arr)//2 #设置步长 6 # count = 0 #用于统计排序进行了多少次数据交换次数 7 # loop = 0 #用于统计排序进行了多少次循环 8 while True: 9 # loop += 1 10 for i in range(step, len(arr)): 11 #每趟排序的次数 12 # loop += 1 13 for j in range(i-step, -1, -step): 14 #每趟排序进行的数据比较交换交换 15 # loop += 1 16 if(arr[j] > arr[j+step]): 17 arr[j], arr[j+step] = arr[j+step], arr[j] 18 # count += 1 19 else: 20 break 21 if step == 1: 22 # print("希尔排序进行了%s循环和%s次数据交换" % (loop, count)) 23 break 24 25 step = step//2 26 27 def insertSort(arr): 28 '''对传入的序列进行插入排序 ''' 29 # count = 0 #用于统计排序进行了多少次数据交换次数 30 # loop = 0 #用于统计排序进行了多少次循环 31 for i in range(1, len(arr)): 32 # loop += 1 33 for j in range(i, 0, -1): 34 # loop += 1 35 if (arr[j] < arr[j-1]): 36 arr[j], arr[j-1] = arr[j-1], arr[j] 37 # count += 1 38 else: 39 break 40 # print("插入排序进行了%s循环和%s次数据交换" %(loop, count)) 41 42 def mkArr(n=10): 43 '''产生一个有n个数据的随机序列，并返回该序列''' 44 ret = [] 45 for i in range(n): 46 ret.append(random.randint(1, n*5+1)) 47 return ret 48 49 def checkSort(arr): 50 '''检测序列是否是一个从小到大排序的序列''' 51 checked = True 52 for i in range(0,len(arr)-1): 53 #检测序列中是否存在一个数比它后面那个数大 54 if (arr[i] > arr[i+1]): 55 checked = False 56 break 57 if checked: 58 print("序列已经排好序。") 59 else: 60 print("序列没有排好序。") 61 return checked 62 63 if __name__ == '__main__': 64 ret = mkArr(10) 65 checkSort(ret) 66 print(ret) 67 shellSort(ret) 68 # insertSort(ret) 69 checkSort(ret) 70 print(ret)
Python源代码
版权声明：本文为1-6-0原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。