《2021年数据结构与算法之排序(归纳总结一) 电脑资料》由会员分享，可在线阅读，更多相关《2021年数据结构与算法之排序(归纳总结一) 电脑资料（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法之排序(归纳总结一) 电脑资料 排序使我们实际 _中最常使用到的几个算法之一，按照如果按照排序过程中依据的原则对内部排序进行分类，则大致上可以分为插入排序、交换排序、选择排序、归并排序等排序方法， 1.直接插入排序 a.算法描述 直接插入排序是一种最简单的插入排序方法，它的基本思想是：仅有一个元素的序列总是有序的，因此，对n个记录的序列，可从第二个元素开始直到第n个元素，逐个向有序序列中执行插入操作，从而得到n个元素按关键字有序的序列。一般来说，在含有j-1 个元素的有序序列中插入一个元素的方法是：从第j-1 个元素开始依次向前搜索应当插入的位置，并且在搜索插入位置的同时可以后移
2、元素，这样当找到适当的插入位置时即可直接插入元素。以关键字序列 26 , 53 , 48 , 11 , 13 , 48, 32 , 15为例，直接插入排序的过程如下所示。 b:算法实现 public void insertSort(int r, int low, int high) for (int i = low + 1; i = low & pare(temp, rj); j-) rj + 1 = rj; / 记录后移 rj + 1 = temp; / 插入到正确位置 【效率分析】 空间效率：仅使用一个辅存单元。 时间效率：假设待排序的元素个数为n，则向有序表中逐个插入记录的操作进行了n-
3、1趟，每趟操作分为比较关键码和 _记录，而比较的次数和 _记录的次数取决于待排序列按关键码的初始排列。直接插入排序的时间复杂度为O(n?) c:实现举例 StraightInsertionSort.java package .test.sort.insertion; public class StraightInsertionSort /* * param args */ public static void _in(String args) / TODO Auto-generated method stub System.out.println(直接插入排序排序功能实现); int arr
4、= 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 ; StraightInsertionSort sort = new StraightInsertionSort(); System.out.println(排序之前序列：); sort.printArr(arr); sort.insertSort(arr, 0, arr.length - 1); System.out.println(排序之后序列：); sort.printArr(arr); public void insertSort(int r, int low, int high) for (int i =
5、 low + 1; i = low & pare(temp, rj); j-) rj + 1 = rj; / 记录后移 rj + 1 = temp; / 插入到正确位置 public boolean pare(int paramA, int paramB) if (paramA tj（i 按步长序列个数k，对待排序元素序列进行k趟排序； 每趟排序，根据对应的步长ti，将待排序列分割成ti个子序列，分别对各子序列进行直接插入排序。当步长因子为1时，所有元素作为一个序列来处理，其长度为n。以关键字序列 26 , 53 , 67 , 48 , 57 , 13 , 48, 32 , 60 , 50为例
6、，假设选择的步长序列为5 , 3 , 1，则希尔排序的过程如图9-2所示。因为步长序列长度为3，因此对待排序序列一共需要进行3趟排序。首先，第一趟排序中将关键字序列分成5个子序列26 , 13，53 , 48，67 , 32，48 , 60，57 , 50，对它们分别进行直接插入排序，结果如图所示。然后，进行第二趟希尔排序，此时步长为3，则将关键字序列分成3个子序列13 , 48 , 53 , 57，48, 50 , 67，32 , 26 , 60，对它们进行直接插入排序后的结果如图所示。最后，对整个序列进行一趟直接插入排序，此时得到一个关键字有序的序列，希尔排序结束。 b.算法实现 publ
7、ic void shellSort(int r, int low, int high, int delta) for (int k = 0; k delta.length; k+) shellInsert(r, low, high, deltak); / 一趟步长为deltak的直接插入排序 private void shellInsert(int r, int low, int high, int deltaK) for (int i = low + deltaK; i = low & pare(temp, rj); j = j - deltaK) rj + deltaK = rj; / 记
8、录后移 j; rj + deltaK = temp; / 插入到正确位置 【效率分析】 空间效率：仅使用一个辅存单元。 时间效率：假设待排序的元素个数为n，则向有序表中逐个插入记录的操作进行了n-1趟，每趟操作分为比较关键码和 _记录，而比较的次数和 _记录的次数取决于待排序列按关键码的初始排列。直接插入排序的时间复杂度为O(n?) c.使用示例 HashInsertSort.java package .test.sort.insertion; public class HashInsertSort /* * param args */ public static void _in(Strin
9、g args) / TODO Auto-generated method stub System.out.println(希尔排序功能实现); int arr = 23, 54, 6, 2, 65, 34, 2, 67, 7, 9, 43 ; int delta = 5,3,1; HashInsertSort sort = new HashInsertSort(); System.out.println(排序之前序列：); sort.printArr(arr); sort.shellSort(arr, 0, arr.length - 1,delta); System.out.println(排
10、序之后序列：); sort.printArr(arr); public void shellSort(int r, int low, int high, int delta) for (int k = 0; k delta.length; k+) shellInsert(r, low, high, deltak); / 一趟步长为deltak的直接插入排序 private void shellInsert(int r, int low, int high, int deltaK) for (int i = low + deltaK; i = low & pare(temp, rj); j =
11、j - deltaK) rj + deltaK = rj; / 记录后移 j; rj + deltaK = temp; / 插入到正确位置 public boolean pare(int paramA, int paramB) if (paramA paramB) return true; else return false; /* * 依次打印出数组元素 */ public void printArr(int arr) if (arr != null) for (int temp : arr) System.out.print(temp + ); System.out.println(); d.结果输出 3.折半插入排序 a.算法描述 直接插入排序算法简便、容易实现， b.算法实现 public void binInsertSort(int r, i
