本文共 27532 字,大约阅读时间需要 91 分钟。
冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的气泡一样逐渐向上冒。
优化:因为排序的过程中, 各元素不断接近自己的位置, 如果一趟比较下来没有进行过交换, 就说明序列有序, 因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。 从而减少不必要的比较。 (这里说的优化, 可以在冒泡排序写好后, 再进行)
比较相邻的元素。如果第一个比第二个大,就交换它们两个;
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素就是最大的数;
排除最大的数,接着下一轮继续相同的操作,确定第二大的数…
重复步骤1-3,直到排序完成。
淡蓝色表示还未进行排序,绿色表示正在进行比较排序,橙色表示已完成排序
/** * 冒泡排序 */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趟排序的结果[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²)
选择排序也属于内部排序法,是从预排序的数据中,按指定的规则选出某一个元素,再依规定交换位置后打到排序的目的。
第一轮,找到最小的元素,和数组第一个数交换位置。
第二轮,找到第二小的元素,和数组第二个数交换位置…
直到最后一个元素,排序完成。
原始的数组:10,34,40,1
第一轮排序:1,[34,40,10] 下一轮排序在后面3个数中找到最小元素,进行比较交换…
第二轮排序:1,10,[40,34] 下一轮排序在后面2个数中找到最小元素,进行比较交换…
第三轮排序:1,10,34,40
完成排序!
淡蓝色表示还未进行排序,红色表示两个值进行最小值比较,绿色表示正在查找最小值,橙色表示已找出最小值
// 使用逐步推导的方式来,讲解选择排序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)); } }}
第1轮交换的值[1, 34, 40, 10]第2轮交换的值[1, 10, 40, 34]第3轮交换的值[1, 10, 34, 40]
默认为从小到大排序,如要从大到小排序只需将 min > arr[j] 改为 min < arr[j] 即可
平均时间复杂度:O(n²)
插入式排序属于内部排序法,是对于预排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。
把 n 个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素, 无序表中包含有 n-1 个元素, 排序过程中每次从无序表中取出第一个元素, 把它的排序码依次与有序表元素的排序码进行比较, 将它插入到有序表中的适当位置, 使之成为新的有序表。
淡蓝色表示还未进行排序,红色表示待插入的数,绿色表示正在进行排序,橙色表示已完成排序
// 使用逐步推导的方式来讲解,便于理解 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)); } }}
第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²)
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
也就是说,把数组分割成若干(h)个小组(一般数组长度length/2),然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小,h/2->h/4->h/8,并且进行排序,保证有序。当h=1时,则数组排序完成。
// 使用逐步推导的方式来编写希尔排序 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)); } }}
希尔排序第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
快速排序(Quicksort)是对冒泡排序的一种改进。面试最喜欢问的排序算法。这是运用分治法的一种排序算法。
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
/** * 快速排序 */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); } }}
快速排序后:[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
归并排序(MERGE-SORT) 是利用归并的思想实现的排序方法, 该算法采用经典的分治(divide-and-conquer)策略
分治法将问题分(divide)成一些小的问题然后递归求解, 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起, 即分而治之。
归并排序是采用分治法的典型应用,而且是一种稳定的排序方式,不过需要使用到额外的空间。
/** * 归并排序 */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; } }}
归并排序后=[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
1)基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
2)基数排序法是属于稳定性的排序,基数排序法的效率高的稳定性排序法
3)基数排序(Radix sort)是桶排序的扩展
4)基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。
将所有待比较数值统一为同样的数位长度, 数位较短的数前面补零。然后, 从最低位开始, 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
// 使用逐步推导的方式来讲解,便于理解 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)); } }}
第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
基数排序是对传统桶排序的扩展, 速度很快
基数排序是经典的空间换时间的方式, 占用内存很大,当对海量数据排序时, 容易造成 OutOfMemoryError 。
基数排序时稳定的。 [注:假定在待排序的记录序列中, 存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, r[i]=r[j], 且 r[i]在 r[j]之前, 而在排序后的序列中, r[i]仍在 r[j]之前,则称这种排序算法是稳定的; 否则称为不稳定的]
有负数的数组, 我们不用基数排序来进行排序, 如果要支持负数, 参考: https://code.i-harness.com/zh-CN/q/e98fa9
大顶堆举例说明
小顶堆举例说明
/** * 堆排序 */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值放到调整后的位置 }}
数组= [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
转载地址:http://hkiwi.baihongyu.com/