2. it技术
  3. 排序算法

排序算法

it2024-08-01  38

一、冒泡排序 [了解]

1.1 基本介绍

冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

优化：因为排序的过程中， 各元素不断接近自己的位置， 如果一趟比较下来没有进行过交换， 就说明序列有序， 因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。 从而减少不必要的比较。 (这里说的优化， 可以在冒泡排序写好后， 再进行)

1.2 思路

比较相邻的元素。如果第一个比第二个大，就交换它们两个；

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；

排除最大的数，接着下一轮继续相同的操作，确定第二大的数…

重复步骤1-3，直到排序完成。

1.3 动画演示

淡蓝色表示还未进行排序，绿色表示正在进行比较排序，橙色表示已完成排序

1.4 代码示例

/** * 冒泡排序 */ public class BubbleSort { public static void main(String[] args) { int[] arr = {3,1,9,10,2}; bubbleSort(arr); } public static void bubbleSort(int[] arr) { int temp = 0; // 临时变量 boolean flag = false; // 标识变量，表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的大，则交换 if (arr[j] > arr[j+1]) { flag = true; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } System.out.println("第" + (i+1) + "趟排序的结果"); System.out.println(Arrays.toString(arr)); if (!flag) { // 在该趟排序中，没有发生过交换，跳出循环 break; } else { flag = false; // 重置flag，进行下次判断 } } } }

1.5 程序执行结果

第1趟排序的结果 [1, 3, 9, 2, 10] 第2趟排序的结果 [1, 3, 2, 9, 10] 第3趟排序的结果 [1, 2, 3, 9, 10] 第4趟排序的结果 [1, 2, 3, 9, 10]

平均时间复杂度：O(n²)

二、选择排序 [了解]

2.1 基本介绍

选择排序也属于内部排序法，是从预排序的数据中，按指定的规则选出某一个元素，再依规定交换位置后打到排序的目的。

2.2 思路

第一轮，找到最小的元素，和数组第一个数交换位置。

第二轮，找到第二小的元素，和数组第二个数交换位置…

直到最后一个元素，排序完成。

原始的数组：10，34，40，1

第一轮排序：1，[34，40，10] 下一轮排序在后面3个数中找到最小元素，进行比较交换…

第二轮排序：1，10，[40，34] 下一轮排序在后面2个数中找到最小元素，进行比较交换…

第三轮排序：1，10，34，40

完成排序！

2.3 动画演示

淡蓝色表示还未进行排序，红色表示两个值进行最小值比较，绿色表示正在查找最小值，橙色表示已找出最小值

2.4 代码示例

// 使用逐步推导的方式来，讲解选择排序 public static void selectSort2(int[] arr) { // 第1轮 int minIndex = 0; int min = arr[0]; for (int j = 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr[0], 即交换 if (minIndex != 0) { arr[minIndex] = arr[0]; arr[0] = min; } System.out.println("第1轮后~~"); System.out.println(Arrays.toString(arr));// 1, 34, 40, 10 // 第2轮 minIndex = 1; min = arr[1]; for (int j = 2; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr[1], 即交换 // 如果说最小值的索引是跟当前我们设定的最小值索引相同的， // 则说明我们假定的最小值即是最小值，否则，就将最小值与之交换 if (minIndex != 1) { arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第2轮后~~"); System.out.println(Arrays.toString(arr));// 1, 10, 40, 34 // 第3轮 minIndex = 2; min = arr[2]; for (int j = 3; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr[2], 即交换 if (minIndex != 2) { arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第3轮后~~"); System.out.println(Arrays.toString(arr));// 1, 10, 34, 40 } ------ 第1轮后~~ [1, 34, 40, 10] 第2轮后~~ [1, 10, 40, 34] 第3轮后~~ [1, 10, 34, 40] /** * 选择排序 */ public class SelectSort { public static void main(String[] args) { int[] arr = {10,34,40,1}; selectSort(arr); } public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; // 假定最小值的索引 int min = arr[i]; // 假定最小值 for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值并不是最小 min = arr[j]; // 重置 min minIndex = j; // 重置 minIndex } } // 将最小值与之交换 // 如果说最小值的索引是跟当前我们设定的最小值索引相同的， // 则说明我们假定的最小值即是最小值，否则，就将最小值与之交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } System.out.println("第" + (i+1) + "轮交换的值"); System.out.println(Arrays.toString(arr)); } } }

2.5 程序执行结果

第1轮交换的值 [1, 34, 40, 10] 第2轮交换的值 [1, 10, 40, 34] 第3轮交换的值 [1, 10, 34, 40]

默认为从小到大排序，如要从大到小排序只需将 min > arr[j] 改为 min < arr[j] 即可

平均时间复杂度：O(n²)

三、插入排序 [熟悉]

3.1 基本介绍

插入式排序属于内部排序法，是对于预排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

3.2 思路

把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素， 无序表中包含有 n-1 个元素， 排序过程中每次从无序表中取出第一个元素， 把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置， 使之成为新的有序表。

3.3 动画演示

淡蓝色表示还未进行排序，红色表示待插入的数，绿色表示正在进行排序，橙色表示已完成排序

3.4 代码示例

// 使用逐步推导的方式来讲解，便于理解 public static void insertSort2(int[] arr) { // 第1轮 {34,10,40,1} => {10,34,40,1} int insertVal = arr[1]; // 定义待插入的数 int insertIndex = 0; // 定义待插入的下标，即 arr[1]前面的这个数的下标 // 在数组中找到一个比当前遍历的数，小的第一个数 // insertIndex >= 0保证在给 insertVal找插入位置时，不越界 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // arr[1]:10 < arr[0]:34 // 把比当前遍历的数，大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; // arr[1]:10 = arr[0]:34 //需要插入的数的下标往前移动 insertIndex--; // -1 } //插入到这个数的后面 arr[insertIndex + 1] = insertVal; // arr[0]:34 = arr[1]:10 System.out.println("第1轮插入"); System.out.println(Arrays.toString(arr)); // 第2轮 {10,34,40,1} => {10,34,40,1} insertVal = arr[2]; // 定义待插入的数 insertIndex = 1; // 定义待插入的下标，即 arr[2]前面的这个数的下标 // 在数组中找到一个比当前遍历的数，小的第一个数 // insertIndex >= 0保证在给 insertVal找插入位置时，不越界 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // arr[2]:40 < arr[1]:34,不满足，退出循环 // 把比当前遍历的数，大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; // //需要插入的数的下标往前移动 insertIndex--; } //插入到这个数的后面 arr[insertIndex + 1] = insertVal; // arr[2]:40 = arr[2]:40,没有发生交换 System.out.println("第2轮插入"); System.out.println(Arrays.toString(arr)); // 第3轮 {10,34,40,1} => {1,10,34,40} insertVal = arr[3]; // 定义待插入的数 insertIndex = 2; // 定义待插入的下标，即 arr[3]前面的这个数的下标 // 在数组中找到一个比当前遍历的数，小的第一个数 // insertIndex >= 0保证在给 insertVal找插入位置时，不越界 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // ① arr[3]:1 < arr[2]:40 ②依次类推... // 把比当前遍历的数，大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; // ① arr[3]:1 = arr[2]:40 ②依次类推... //需要插入的数的下标往前移动 insertIndex--; // ① 1 ② 0 ③ -1 } //插入到这个数的后面 arr[insertIndex + 1] = insertVal; // ① arr[2]:40 = arr[3]:1 ②依次类推... System.out.println("第3轮插入"); System.out.println(Arrays.toString(arr)); } ------ 第1轮插入 [10, 34, 40, 1] 第2轮插入 [10, 34, 40, 1] 第3轮插入 [1, 10, 34, 40]

arr[insertIndex + 1] = arr[insertIndex] ： 作用：把大的元素放到后面 insertIndex-- ：作用：是对有序表中的元素再进行大小的比对

/** * 插入排序 */ public class InsertSort { public static void main(String[] args) { int[] arr = {34,10,40,1}; // insertSort2(arr); insertSort(arr); } public static void insertSort(int[] arr) { int insertVal = 0; int insertIndex = 0; for (int i = 0; i < arr.length - 1; i++) { insertVal = arr[i+1]; // 定义待插入的数 insertIndex = i; // 定义待插入的下标，即 arr[1]前面的这个数的下标 // 在数组中找到一个比当前遍历的数，小的第一个数 // insertIndex >= 0保证在给 insertVal找插入位置时，不越界 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // arr[1]:10 < arr[0]:34 // 把比当前遍历的数，大的数字往后移动 arr[insertIndex + 1] = arr[insertIndex]; // arr[1]:10 = arr[0]:34 //需要插入的数的下标往前移动 insertIndex--; // -1 } //插入到这个数的后面 arr[insertIndex + 1] = insertVal; // arr[0]:34 = arr[1]:10 System.out.println("第" + (i+1) + "轮插入"); System.out.println(Arrays.toString(arr)); } } }

3.5 程序执行结果

第1轮插入 [10, 34, 40, 1] 第2轮插入 [10, 34, 40, 1] 第3轮插入 [1, 10, 34, 40] int[] arr = {34,10,40,1,7,50}; 第1轮插入 [10, 34, 40, 1, 7, 50] 第2轮插入 [10, 34, 40, 1, 7, 50] 第3轮插入 [1, 10, 34, 40, 7, 50] 第4轮插入 [1, 7, 10, 34, 40, 50] 第5轮插入 [1, 7, 10, 34, 40, 50]

默认为从小到大排序，如要从大到小排序只需将 insertVal < arr[insertIndex] 改为 insertVal > arr[insertIndex] 即可

平均时间复杂度：O(n²)

四、希尔排序 [了解]

4.1 基本介绍

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

4.2 思路

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

也就是说，把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

4.3 图解示例

4.4 代码示例

// 使用逐步推导的方式来编写希尔排序 public static void shellSortExchange2(int[] arr) { int temp = 0; // 希尔排序的第 1轮排序 // 因为第 1轮排序，是将 10个数据分成了 5组 for (int i = 5; i < arr.length; i++) { // 遍历各组中所有的元素(共 5组，每组有 2个元素), 步长 5 for (int j = i - 5; j >= 0; j -= 5) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + 5]) { temp = arr[j]; arr[j] = arr[j + 5]; arr[j + 5] = temp; } } } System.out.println("希尔排序第1轮=" + Arrays.toString(arr)); // 希尔排序的第 2轮排序 // 因为第 2轮排序，是将 10个数据分成了 5/2 = 2组 for (int i = 2; i < arr.length; i++) { // 遍历各组中所有的元素(共 5组，每组有 2个元素), 步长 2 for (int j = i - 2; j >= 0; j -= 2) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + 2]) { temp = arr[j]; arr[j] = arr[j + 2]; arr[j + 2] = temp; } } } System.out.println("希尔排序第2轮=" + Arrays.toString(arr)); // 希尔排序的第 3轮排序 // 因为第 3轮排序，是将10个数据分成了 2/2 = 1组 for (int i = 1; i < arr.length; i++) { // 遍历各组中所有的元素(共 5组，每组有 2个元素), 步长1 for (int j = i - 1; j >= 0; j -= 1) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } System.out.println("希尔排序第3轮=" + Arrays.toString(arr)); } ------ 希尔排序第1轮=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 希尔排序第2轮=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] 希尔排序第3轮=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] /** * 希尔排序 */ public class ShellSort { public static void main(String[] args) { int[] arr = {8,9,1,7,2,3,5,4,6,0}; // 交换法 shellSortExchange2(arr); // shellSortExchange(arr); // 移位法 // shellSortDisplaced(arr); } // 对交换式的希尔排序进行优化 -> 移位法 public static void shellSortDisplaced(int[] arr) { // 增量gap, 并逐步的缩小增量 int count = 0; for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素，逐个对其所在的组进行直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { // 移动 arr[j] = arr[j - gap]; j -= gap; } // temp 比 arr[j - gap] 大，所以需要插入在 j 的位置 arr[j] = temp; } } System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(arr)); } } public static void shellSortExchange(int[] arr) { int temp = 0; int count = 0; // 增量 gap，并逐步的缩小增量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { // 遍历各组中所有的元素(共 gap组，每组有 2个元素), 步长 gap for (int j = i - gap; j >= 0; j -= gap) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(arr)); } } }

4.5 程序执行结果

希尔排序第1轮=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 希尔排序第2轮=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] 希尔排序第3轮=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 创建要给80000个的随机的数组 int[] testArr = new int[80000]; for (int i = 0; i < 80000; i++) { testArr[i] = (int) (Math.random() * 80000); // 生成一个[0, 80000) 数 } long start = System.currentTimeMillis(); // shellSortExchange(testArr); // 交换式 shellSortDisplaced(testArr); // 移位式 long end = System.currentTimeMillis(); System.out.println("移位式程序执行时间(ms)：" + (end - start));

① 交换式程序执行时间(ms)：6299 ② 6131ms ③ 6268ms

① 移位式程序执行时间(ms)：27 ② 22ms ③ 22ms

五、快速排序 [重点]

5.1 基本介绍

快速排序(Quicksort)是对冒泡排序的一种改进。面试最喜欢问的排序算法。这是运用分治法的一种排序算法。

5.2 思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

5.3 动画演示

5.4 代码示例

/** * 快速排序 */ public class QuickSort { public static void main(String[] args) { int[] arr = {9,48,10,23,1,37}; quickSort(arr, 0, arr.length - 1); System.out.println("快速排序后：" + Arrays.toString(arr)); } public static void quickSort(int[] arr, int left, int right) { int l = left; // 左索引 int r = right; // 右索引 int pivot = arr[(left + right) / 2]; //中轴 int temp = 0; //临时变量，交换时使用 // 让比 pivot值小的放到左边，比 pivot值大的放到右边 while (l < r) { // 在 pivot的左边一直找，找到大于等于 pivot值才退出 while (arr[l] < pivot) { l++; } // 在 pivot的右边一直找，找到小于等于 pivot值才退出 while (arr[r] > pivot) { r--; } // 如果 l >= r 说明 pivot的左右两边的值已经按照 // 左边全部是小于等于 pivot值，右边全部是大于等于 pivot值 if (l >= r) { break; } // 交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // 如果交换完后，发现这个 arr[l] == pivot值，则 r--，前移 if (arr[l] == pivot) { r--; } // 如果交换完后，发现这个 arr[r] == pivot值，则 l++，后移 if (arr[r] == pivot) { l++; } } // 如果 l==r，必须 l++,r--，否则会出现栈溢出 if (l == r) { l += 1; r -= 1; } // 向左递归 if (left < r) { quickSort(arr, left, r); } // 向右递归 if (right > l) { quickSort(arr, l, right); } } }

5.5 程序执行结果

快速排序后：[1, 9, 10, 23, 37, 48] // 创建要给80000个的随机的数组 int[] testArr = new int[80000]; for (int i = 0; i < 80000; i++) { testArr[i] = (int) (Math.random() * 80000); // 生成一个[0, 80000) 数 } long start = System.currentTimeMillis(); quickSort(testArr, 0, testArr.length - 1); long end = System.currentTimeMillis(); System.out.println("快排耗时(ms)：" + (end - start));

① 快排耗时(ms)：36 ② 24ms ③ 55ms ④ 49ms ⑤ 51ms ⑥ 19ms ⑦ 33ms

六、归并排序 [重点]

6.1 基本介绍

归并排序（MERGE-SORT） 是利用归并的思想实现的排序方法， 该算法采用经典的分治（divide-and-conquer）策略

分治法将问题分(divide)成一些小的问题然后递归求解， 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起， 即分而治之。

归并排序是采用分治法的典型应用，而且是一种稳定的排序方式，不过需要使用到额外的空间。

6.2 思路

把数组不断划分成子序列，划成长度只有2或者1的子序列。然后利用临时数组，对子序列进行排序，合并，再把临时数组的值复制回原数组。反复操作1~2步骤，直到排序完成。

6.3 动画演示

6.4 代码示例

/** * 归并排序 */ public class MergerSort { public static void main(String[] args) { int[] arr = {8,4,5,7,1,3,6,2}; int[] temp = new int[arr.length]; // 归并排序需要一个额外空间 mergeSort(arr, 0, arr.length - 1, temp); System.out.println("归并排序后=" + Arrays.toString(arr)); } // 分+合方法 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; // 中间索引 // 向左递归进行分解 mergeSort(arr, left, mid, temp); // 向右递归进行分解 mergeSort(arr, mid + 1, right, temp); // 合并 merger(arr, left, mid, right, temp); } } /** * 合并的方法 * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ public static void merger(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 初始化i, 左边有序序列的初始索引 int j = mid + 1; // 初始化j, 右边有序序列的初始索引 int t = 0; // 指向temp数组的当前索引 // (一) // 先把左右两边(有序)的数据按照规则填充到temp数组 // 直到左右两边的有序序列，有一边处理完毕为止 while (i <= mid && j <= right) {// 继续 // 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素 // 即将左边的当前元素，填充到 temp数组 // 然后 t++, i++ if (arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else { // 反之,将右边有序序列的当前元素，填充到temp数组 temp[t] = arr[j]; t += 1; j += 1; } } // (二) // 把有剩余数据的一边的数据依次全部填充到temp while (i <= mid) { // 左边的有序序列还有剩余的元素，就全部填充到temp temp[t] = arr[i]; t += 1; i += 1; } while (j <= right) { // 右边的有序序列还有剩余的元素，就全部填充到temp temp[t] = arr[j]; t += 1; j += 1; } // (三) // 将temp数组的元素拷贝到arr // 注意，并不是每次都拷贝所有 t = 0; int tempLeft = left; // // 第一次合并 tempLeft = 0 , right = 1 //第二次： tempLeft = 2 right = 3 //第三次： tL=0 ri=3 // 最后一次 tempLeft = 0 right = 7 while (tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } }

6.5 程序执行结果

归并排序后=[1, 2, 3, 4, 5, 6, 7, 8] // 测试快排的执行速度 // 创建要给80000个的随机的数组 int[] testArr = new int[80000]; int[] testTemp = new int[testArr.length]; for (int i = 0; i < 80000; i++) { testArr[i] = (int) (Math.random() * 80000); // 生成一个[0, 80000) 数 } long start = System.currentTimeMillis(); mergeSort(testArr, 0, testArr.length - 1, testTemp); long end = System.currentTimeMillis(); System.out.println("归并排序耗时(ms)：" + (end - start));

① 归并排序耗时(ms)：20 ② 25ms ③ 22ms

七、基数排序 [了解]

7.1 基本介绍

1）基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

2）基数排序法是属于稳定性的排序，基数排序法的效率高的稳定性排序法

3）基数排序(Radix sort)是桶排序的扩展

4）基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

7.2 思路

将所有待比较数值统一为同样的数位长度， 数位较短的数前面补零。然后， 从最低位开始， 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

7.3 动画演示

7.4 代码示例

// 使用逐步推导的方式来讲解，便于理解 public static void radixSort2(int[] arr) { // 第 1轮（对每个元素的个位数进行排序） // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数 //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 int[] bucketElementCounts = new int[10]; for(int j = 0; j < arr.length; j++) { //取出每个元素的个位的值 int digitOfElement = arr[j] % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组) int index = 0; //遍历每一桶，并将桶中是数据，放入到原数组 for(int k = 0; k < bucketElementCounts.length; k++) { //如果桶中，有数据，我们才放入到原数组 if(bucketElementCounts[k] != 0) { //循环该桶即第k个桶(即第k个一维数组), 放入 for(int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第 l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第1轮，对个位的排序处理arr= " + Arrays.toString(arr)); // 第 2轮（对每个元素的十位数进行排序） for(int j = 0; j < arr.length; j++) { //取出每个元素的个位的值 int digitOfElement = arr[j] /10 % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组) index = 0; //遍历每一桶，并将桶中是数据，放入到原数组 for(int k = 0; k < bucketElementCounts.length; k++) { //如果桶中，有数据，我们才放入到原数组 if(bucketElementCounts[k] != 0) { //循环该桶即第k个桶(即第k个一维数组), 放入 for(int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第 l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第2轮，对个位的排序处理arr= " + Arrays.toString(arr)); // 第 3轮（对每个元素的十位数进行排序） for(int j = 0; j < arr.length; j++) { //取出每个元素的个位的值 int digitOfElement = arr[j] /100 % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组) index = 0; //遍历每一桶，并将桶中是数据，放入到原数组 for(int k = 0; k < bucketElementCounts.length; k++) { //如果桶中，有数据，我们才放入到原数组 if(bucketElementCounts[k] != 0) { //循环该桶即第k个桶(即第k个一维数组), 放入 for(int l = 0; l < bucketElementCounts[k]; l++) { //取出元素放入到arr arr[index++] = bucket[k][l]; } } //第 l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第3轮，对个位的排序处理arr= " + Arrays.toString(arr)); } ------ 第1轮，对个位的排序处理arr= [542, 53, 3, 14, 214, 748] 第2轮，对个位的排序处理arr= [3, 14, 214, 542, 748, 53] 第3轮，对个位的排序处理arr= [3, 14, 53, 214, 542, 748] - 排序的轮数与数组中最大的位数有关 /** * 基数排序 */ public class RadixSort { public static void main(String[] args) { int[] arr = {53,3,542,748,14,214}; // radixSort2(arr); radixSort(arr); } public static void radixSort(int[] arr) { // 1.获得数组中最大的数 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } // 得到最大数是几位数 int maxLength = (max + "").length(); // 2.定义一个二维数组，表示10个桶，每个桶就是一个一维数组 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数 //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 int[] bucketElementCounts = new int[10]; // n=1 表示处理个位，n=10表示处理十位，n=100表示处理百位 ...... for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) { //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位，依次类推... for(int j = 0; j < arr.length; j++) { //取出每个元素的对应位的值 int digitOfElement = arr[j] / n % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组) int index = 0; //遍历每一桶，并将桶中的数据，放入到原数组 for(int k = 0; k < bucketElementCounts.length; k++) { //如果桶中，有数据，我们才放入到原数组 // 遍历第k个桶(即第k个一维数组), 将桶中的数据放回原数组中 for (int l = 0; l < bucketElementCounts[k]; l++) { // 取出元素放入到arr arr[index++] = bucket[k][l]; } //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！ bucketElementCounts[k] = 0; } System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr)); } } }

7.5 程序执行结果

第1轮，对个位的排序处理 arr =[542, 53, 3, 14, 214, 748] 第2轮，对个位的排序处理 arr =[3, 14, 214, 542, 748, 53] 第3轮，对个位的排序处理 arr =[3, 14, 53, 214, 542, 748] // 创建要给80000个的随机的数组 int[] testArr = new int[80000]; for (int i = 0; i < 80000; i++) { testArr[i] = (int) (Math.random() * 80000); // 生成一个[0, 80000) 数 } long start = System.currentTimeMillis(); radixSort(testArr); long end = System.currentTimeMillis(); System.out.println("基数排序耗时(ms)：" + (end - start));

① 基数排序耗时(ms)：36 ② 15ms ③ 41ms ④ 38ms ⑤ 37ms ⑥ 33ms

7.6 基数排序说明

基数排序是对传统桶排序的扩展， 速度很快

基数排序是经典的空间换时间的方式， 占用内存很大，当对海量数据排序时， 容易造成 OutOfMemoryError 。

基数排序时稳定的。 [注：假定在待排序的记录序列中， 存在多个具有相同的关键字的记录， 若经过排序， 这些记录的相对次序保持不变， 即在原序列中， r[i]=r[j]， 且 r[i]在 r[j]之前， 而在排序后的序列中， r[i]仍在 r[j]之前，则称这种排序算法是稳定的； 否则称为不稳定的]

有负数的数组， 我们不用基数排序来进行排序, 如果要支持负数， 参考: https://code.i-harness.com/zh-CN/q/e98fa9

八，堆排序 [重点]

8.1 基本介绍

堆排序是利用堆这种数据结构而设计的一种排序算法， 堆排序是一种选择排序， 它的最坏， 最好， 平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 称为大顶堆，注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。每个结点的值都小于或等于其左右孩子结点的值， 称为小顶堆

大顶堆举例说明

小顶堆举例说明

8.2 思路

将待排序序列构造成一个大顶堆此时， 整个序列的最大值就是堆顶的根节点将其与末尾元素进行交换， 此时末尾就为最大值然后将剩余 n-1 个元素重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了 可以看到在构建大顶堆的过程中， 元素的个数逐渐减少， 最后就得到一个有序序列了

8.3 代码示例

/** * 堆排序 */ public class HeapSort { public static void main(String[] args) { int[] arr = {4, 6, 8, 5, 9}; heapSort(arr); } public static void heapSort(int[] arr) { int temp = 0; // 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } /* * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端; * 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 */ for (int j = arr.length - 1; j > 0; j--) { // 交换 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } System.out.println("数组= " + Arrays.toString(arr)); } /** * 将一个数组(二叉树), 调整成一个大顶堆 * * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 * 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6} * 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4} * * @param arr 待调整的数组 * @param i 表示非叶子结点在数组中索引 * @param length 表示对多少个元素继续调整， length 是在逐渐的减少 */ public static void adjustHeap(int[] arr, int i, int length) { int temp = arr[i];// 先取出当前元素的值，保存在临时变量 // 开始调整 // 说明 // 1. k = i * 2 + 1 ：k 是 i结点的左子结点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { if (k + 1 < length && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值 k++; // k 指向右子结点 } if (arr[k] > temp) { // 如果子结点大于父结点 arr[i] = arr[k]; // 把较大的值赋给当前结点 i = k; // !!! i 指向 k，将小的值沉下去 } else { break; // ! 由于是从最深处往前调整，下面的子树已经是大顶堆了 } } // 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部) arr[i] = temp;// 将temp值放到调整后的位置 } }

8.4 程序执行结果

数组= [4, 5, 6, 8, 9] // 创建要给80000个的随机的数组 int[] testArr = new int[80000]; for (int i = 0; i < 80000; i++) { testArr[i] = (int) (Math.random() * 80000); // 生成一个[0, 80000) 数 } long start = System.currentTimeMillis(); heapSort(testArr); long end = System.currentTimeMillis(); System.out.println("堆排序耗时(ms)：" + (end - start));

① 堆排序耗时(ms)：11 ② 14ms ③ 10ms ④ 11ms ⑤ 13ms ⑥ 15ms

常用排序算法总结何对比

1、比较图

2、相关术语解释

稳定：如果 a 原本在 b 前面， 而 a=b， 排序之后 a 仍然在 b 的前面；不稳定：如果 a 原本在 b 的前面， 而 a=b， 排序之后 a 可能会出现在 b 的后面；内排序： 所有排序操作都在内存中完成；外排序： 由于数据太大， 因此把数据放在磁盘中， 而排序通过磁盘和内存的数据传输才能进行；时间复杂度： 一个算法执行所耗费的时间；空间复杂度： 运行完一个程序所需内存的大小；n: 数据规模；k: “桶” 的个数；In-place：不占用额外内存；Out-place：占用额外内存。
最新回复(0)