Loading... 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 <!--more--> ![](https://s1.ax1x.com/2020/09/21/wbQDeO.png) **快速排序**:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; ## 插入排序:直接插入排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/20 * <p> * (直接)插入排序(越接近正序性能越好) * 时间复杂度:平均O(N^2)、最坏O(N^2)、最好O(N) * 空间复杂度:O(1) * 稳定性:稳定 * 复杂性:简单 */ public class InsertSort { public void insertSort(int[] list) { //第0趟直接第一个元素 System.out.format("第 0 趟: %d\n", list[0]); for (int i = 1; i < list.length; i++) { int j; int temp = list[i]; //如果比顺序的最后一个大,则直接不走for插入到最后面。否则比temp大元素后移 for (j = i - 1; j >= 0 && temp < list[j]; j--) { list[j + 1] = list[j]; } //temp为最小时j=-1 list[j + 1] = temp; System.out.format("第 %d 趟: ", i); printPart(list,0,i); } } public void printPart(int[] list, int begin, int end) { for (int i = 0; i < begin; i++) { System.out.print(" "); } for (int i = begin; i <= end; i++) { System.out.print(list[i] + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } InsertSort insert = new InsertSort(); System.out.print("排序前: "); insert.printPart(array, 0, array.length - 1); insert.insertSort(array); System.out.print("排序后: "); insert.printPart(array, 0, array.length - 1); } } ``` --- ## 插入排序:希尔排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/20 * <p> * 希尔排序(缩小增量排序、加强版的直接插入排序) * 时间复杂度:平均O(Nlog2N)、最坏O(N^1.5) * 空间复杂度:O(1) * 稳定性:不稳定 * 复杂性:较复杂 */ public class ShellSort { public void shellSort(int[] list) { //按步长gap分组,每组都进行直接插入排序 int gap = list.length / 2; while (gap >= 1) { //调用直接插入排序的算法,除了此处i++,其余1都替换为gap for (int i = gap; i < list.length; i++) { int j; int temp = list[i]; for (j = i - gap; j >= 0 && temp < list[j]; j -= gap) { list[j + gap] = list[j]; } list[j + gap] = temp; } System.out.format("gap = %d: ", gap); printAll(list); gap /= 2; } } public void printAll(int[] list) { for (int value : list) { System.out.print(value + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } ShellSort shell = new ShellSort(); System.out.print("排序前: "); shell.printAll(array); shell.shellSort(array); System.out.print("排序后: "); shell.printAll(array); } } ``` --- ## 选择排序:简单选择排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/20 * <p> * 希尔排序(缩小增量排序、加强版的直接插入排序) * 时间复杂度:平均O(Nlog2N)、最坏O(N^1.5) * 空间复杂度:O(1) * 稳定性:不稳定 * 复杂性:较复杂 */ public class ShellSort { public void shellSort(int[] list) { //按步长gap分组,每组都进行直接插入排序 int gap = list.length / 2; while (gap >= 1) { //调用直接插入排序的算法,除了此处i++,其余1都替换为gap for (int i = gap; i < list.length; i++) { int j; int temp = list[i]; for (j = i - gap; j >= 0 && temp < list[j]; j -= gap) { list[j + gap] = list[j]; } list[j + gap] = temp; } System.out.format("gap = %d: ", gap); printAll(list); gap /= 2; } } public void printAll(int[] list) { for (int value : list) { System.out.print(value + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } ShellSort shell = new ShellSort(); System.out.print("排序前: "); shell.printAll(array); shell.shellSort(array); System.out.print("排序后: "); shell.printAll(array); } } ``` --- ## 选择排序:堆排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/20 * <p> * 堆排序 * 时间复杂度:平均O(Nlog2N)、最坏O(Nlog2N)、最好O(Nlog2N) * 空间复杂度:O(1) * 稳定性:不稳定 * 复杂性:较复杂 */ public class HeapSort { /** * 建立初始堆,只需符合大根堆即可 */ public void heapAdjust(int[] array, int parent, int length) { int temp = array[parent]; int child = 2 * parent + 1; while (child < length) { if (child + 1 < length && array[child] < array[child + 1]) { child++; } if (temp >= array[child]) { break; } array[parent] = array[child]; //针对重新调整为大根堆时 parent = child; child = 2 * parent + 1; } array[parent] = temp; } public void heapSort(int[] list) { //循环建立初始堆,parent为最后一个根节点(自下而上) for (int i = list.length / 2; i >= 0; i--) { heapAdjust(list, i, list.length); } //堆顶和末尾交换,n-1次排序 for (int i = list.length - 1; i > 0; i--) { int temp = list[i]; list[i] = list[0]; list[0] = temp; //重构堆(自上而下) heapAdjust(list, 0, i); System.out.format("第 %d 趟: ", list.length - i); printPart(list, 0, list.length - 1); } } public void printPart(int[] list, int begin, int end) { for (int i = 0; i < begin; i++) { System.out.print(" "); } for (int i = begin; i <= end; i++) { System.out.print(list[i] + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } HeapSort heap = new HeapSort(); System.out.print("排序前: "); heap.printPart(array, 0, array.length - 1); heap.heapSort(array); System.out.print("排序后: "); heap.printPart(array, 0, array.length - 1); } } ``` --- ## 交换排序:冒泡排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/18 * <p> * 冒泡排序(越接近正序性能越好) * 时间复杂度:平均O(N^2)、最坏O(N^2)、最好O(N) * 空间复杂度:O(1) * 稳定性:稳定 * 复杂性:简单 */ public class BubbleSort { public void bubbleSort(int[] list) { int temp; //从后往前冒泡,前面有大的就交换 for (int i = 0; i < list.length - 1; i++) { for (int j = list.length - 1; j > i; j--) { if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; } } System.out.format("第 %d 趟: ", i); printAll(list); } } /** * 优化:加入标志性变量exchange,用于标志某一趟排序过程中是否有数据交换。 * 如果进行某一趟排序时并没有进行数据交换,则说明所有数据已经有序,可立即结束排序。 */ public void bubbleSort2(int[] list) { int temp; boolean bChange; for (int i = 0; i < list.length - 1; i++) { bChange = false; for (int j = list.length - 1; j > i; j--) { if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bChange = true; } } if (!bChange) { break; } System.out.format("第 %d 趟: ", i); printAll(list); } } public void printAll(int[] list) { for (int value : list) { System.out.print(value + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } BubbleSort bubble = new BubbleSort(); System.out.print("排序前: "); bubble.printAll(array); // bubble.bubbleSort(array); bubble.bubbleSort2(array); System.out.print("排序后: "); bubble.printAll(array); } } ``` --- ## 交换排序:快速排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/20 * <p> * 快速排序(越随机性能越好) * 时间复杂度:平均O(Nlog2N)、最坏O(N^2)、最好O(Nlog2N) * 空间复杂度:平均O(logN)、就地快排O(1)、递归平分数组最优O(logN)、递归最差退为冒泡O(N) * 稳定性:不稳定(相等元素可能会因为分区而交换顺序) * 复杂性:较复杂 */ public class QuickSort { public int division(int[] list, int left, int right) { int base = list[left]; //不管有没有找到,只要碰头就结束,再递归成左右两部分(没找到情况下其中一部分为空) while (left < right) { //先从右边开始找 while (left < right && list[right] >= base) { right--; } list[left] = list[right]; //再从左开始找 while (left < right && list[left] <= base) { left++; } list[right] = list[left]; } //左边初始给右边找到的,右边找到的位置给左边找到的位置,左边找到的位置给base list[left] = base; return left; } public void quickSort(int[] list, int left, int right) { if (left < right) { int base = division(list, left, right); System.out.format("base = %d: ", list[base]); printPart(list, left, right); quickSort(list, left, base - 1); quickSort(list, base + 1, right); } } public void printPart(int[] list, int begin, int end) { for (int i = 0; i < begin; i++) { System.out.print(" "); } for (int i = begin; i <= end; i++) { System.out.print(list[i] + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } QuickSort quick = new QuickSort(); System.out.print("排序前: "); quick.printPart(array, 0, array.length - 1); quick.quickSort(array, 0, array.length - 1); System.out.print("排序后: "); quick.printPart(array, 0, array.length - 1); } } ``` --- ## 归并排序 ```Java package algorithm.sort; import java.util.Random; /** * @author 唐宋丶 * @create 2020/9/21 * * 归并排序 * 时间复杂度:平均O(Nlog2N)、最坏O(Nlog2N)、最好O(Nlog2N) * 空间复杂度:O(n) * 稳定性:稳定 * 复杂性:较复杂 */ public class MergeSort { /** * 两段小数组合成一个大数组 * [low,mid][mid+1,high] -> [low,high] */ public void Meger(int[] array, int low, int mid, int high) { //i第一段数组下标、j第二段数组下标、array2临时大数组、k大数组下标 int i = low; int j = mid + 1; int k = 0; int[] array2 = new int[high - low + 1]; //存在两个小数组可能不等长,扫描完一个后停止 while (i <= mid && j <= high) { //从小到大合并两数组 if (array[i] <= array[j]) { array2[k++] = array[i++]; } else { array2[k++] = array[j++]; } } while (i <= mid) { array2[k++] = array[i++]; } while (j <= high) { array2[k++] = array[j++]; } for (k = 0, i = low; i <= high; i++, k++) { array[i] = array2[k]; } } /** * gap为数组[low,mid][mid+1,high] -> [low,high]宽度 * 2 * gap = high - low + 1; (1 2 4 8 ...) */ public void mergePass(int[] array, int gap, int length) { int i; //两个长度相等时合并(2 2 1 -> 4 1 -> 5) for (i = 0; i + 2 * gap - 1 < length; i += 2 * gap) { Meger(array, i, i + gap - 1, i + 2 * gap - 1); } //不够合并时(2 2 2 1 -> 4 3 -> 7) if (i + gap - 1 < length) { Meger(array, i, i + gap - 1, length - 1); } } public void megerSort(int[] list) { for (int gap = 1; gap < list.length; gap *= 2) { mergePass(list, gap, list.length); System.out.format("gap = %d: ", gap); printAll(list); } } public void printAll(int[] list) { for (int value : list) { System.out.print(value + " "); } System.out.println(); } public static void main(String[] args) { final int MAX_SIZE = 7; int[] array = new int[MAX_SIZE]; Random random = new Random(); for (int i = 0; i < MAX_SIZE; i++) { array[i] = random.nextInt(10); } MergeSort merge = new MergeSort(); System.out.print("排序前: "); merge.printAll(array); merge.megerSort(array); System.out.print("排序后: "); merge.printAll(array); } } ``` --- ## 基数排序 ```Java package algorithm.sort; /** * @author 唐宋丶 * @create 2020/9/21 * * 基数排序 * 时间复杂度:平均O(d(n+r))、最坏O(d(n+r))、最好O(d(n+r)) r为基数,d为位数 * 空间复杂度:O(n+r) * 稳定性:稳定 * 复杂性:较复杂 */ public class RadixSort { // 获取x这个数的d位数上的数字 // 比如获取123的1位数,结果返回3 public int getDigit(int x, int d) { int a[] = { 1, 1, 10, 100 }; // 本实例中的最大数是百位数,所以只要到100就可以了 return ((x / a[d]) % 10); } public void radixSort(int[] list, int begin, int end, int digit) { final int radix = 10; // 基数 int i = 0, j = 0; int[] count = new int[radix]; // 存放各个桶的数据统计个数 int[] bucket = new int[end - begin + 1]; // 按照从低位到高位的顺序执行排序过程 for (int d = 1; d <= digit; d++) { // 置空各个桶的数据统计 for (i = 0; i < radix; i++) { count[i] = 0; } // 统计各个桶将要装入的数据个数 for (i = begin; i <= end; i++) { j = getDigit(list[i], d); count[j]++; } // count[i]表示第i个桶的右边界索引 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } // 将数据依次装入桶中 // 这里要从右向左扫描,保证排序稳定性 for (i = end; i >= begin; i--) { j = getDigit(list[i], d); // 求出关键码的第k位的数字, 例如:576的第3位是5 bucket[count[j] - 1] = list[i]; // 放入对应的桶中,count[j]-1是第j个桶的右边界索引 count[j]--; // 对应桶的装入数据索引减一 } // 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表 for (i = begin, j = 0; i <= end; i++, j++) { list[i] = bucket[j]; } } } public int[] sort(int[] list) { radixSort(list, 0, list.length - 1, 3); return list; } // 打印完整序列 public void printAll(int[] list) { for (int value : list) { System.out.print(value + "\t"); } System.out.println(); } public static void main(String[] args) { int[] array = { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 }; RadixSort radix = new RadixSort(); System.out.print("排序前:\t\t"); radix.printAll(array); radix.sort(array); System.out.print("排序后:\t\t"); radix.printAll(array); } } ``` Last modification:August 14, 2022 © Allow specification reprint Like 0 喵ฅฅ