排序

排序算法是程序员入门基础算法，下边我们使用Java语言实现常见内部排序算法。

内部排序：待排序记录全部存放在内存中进行排序的过程。

外部排序：待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

稳定性：若在待排序的序列中 Ai = Aj，排序之前 Ai 领先 Aj ，排序后Ai 和 Aj的相对次序不变， Ai 依然领先 Aj则称此排序算法是稳定的，反之为不稳定。如序列 4 3 4 2 1，用选择排序时，第一趟排序： 第一个4 和 1交换，则两个4之前的相对次序会变化，因此选择排序是不稳定的。

冒泡排序

n个记录进行冒泡排序的方法是：比较相邻两个记录，若逆序则交换这两个值，然后以此类推，第一趟的排序结果是最大的值被交换到第n个记录的位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是次大值被交换到第n-1个记录的位置上。冒泡排序最多需要进行n-1趟。若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]

第一趟排序时从i=0开始，比较 a[0] 和 a[1],5 > 3 则交换 a[0]和a[1]得到[3,5, 7, 6, 4, 1, 0, 2, 9, 10, 8]继续比较a[1]和a[2] 5 < 7 不用交换，继续向后比较a[2]和a[3]依次类推，最终比较a[9]和a[10]将最大值10放在下标为10的位置；得到第一趟排序结果，第二趟排序将次大值9放在下标为9的位置，...直到数组完全有序为止。

第1趟排序结果:[3, 5, 6, 4, 1, 0, 2, 7, 9, 8, 10]

第2趟排序结果:[3, 5, 4, 1, 0, 2, 6, 7, 8, 9, 10]

第3趟排序结果:[3, 4, 1, 0, 2, 5, 6, 7, 8, 9, 10]

第4趟排序结果:[3, 1, 0, 2, 4, 5, 6, 7, 8, 9, 10]

第5趟排序结果:[1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]

第6趟排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

上述序列经过6趟排序，得到完全有序序列，此时排序完成即可结束排序过程。

/** 冒泡排序* nums : 待排数组* */public static void bubbleSort(int[] nums) {for (int i = 1; i < nums.length; i++) {boolean temp =false; // 标记某趟排序是否有值交换for (int j = 0; j < nums.length - i; j++) {if (nums[j] > nums[j + 1]) { // 相邻元素比较，递增排序nums[j] = nums[j] + nums[j + 1];nums[j + 1] = nums[j] - nums[j + 1]; // 元素交换nums[j] = nums[j] - nums[j + 1];temp = true; // 有值交换}}if (!temp) break; // 无值交换结束排序}}

简单选择排序

n个记录进行简单选择排序就是：通过n-i(1<=i<=n)次关键之间的比较，从n-i+1个记录中选出最小值，并和第i个记录交换。简单说就是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择第二小的，依次类推，直到第n - 1个元素。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]

第1趟排序在11个元素中找出0放到下标为0的位置，第二趟排序在剩余10个元素中找到1放到下标为1的位置，...总共11个元素则需要10趟排序，其结果如下:

第1趟排序结果: [0, 3, 7, 6, 4, 1, 5, 2, 9, 10, 8]

第2趟排序结果: [0, 1, 7, 6, 4, 3, 5, 2, 9, 10, 8]

第3趟排序结果: [0, 1, 2, 6, 4, 3, 5, 7, 9, 10, 8]

第4趟排序结果: [0, 1, 2, 3, 4, 6, 5, 7, 9, 10, 8]

第5趟排序结果: [0, 1, 2, 3, 4, 6, 5, 7, 9, 10, 8]

第6趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]

第7趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]

第8趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]

第9趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

第10趟排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

/** 简单选择排序* nums :待排序数组* */public static void selectSort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {int min = i; // min记录最小元素下标，默认当前起始元素为最小for (int j = i + 1; j < nums.length; j++) {if (nums[min] > nums[j]) {// 遍历剩余元素找出最小值min = j;// 记录最小值数据下标}}if (min != i) {// 最小值不为当前元素则交换nums[i] = nums[i] + nums[min];nums[min] = nums[i] - nums[min];nums[i] = nums[i] - nums[min];}}}

直接插入排序

直接插入是一种简单排序方法，在插入第i个元素时，R1 、R2 ...、Ri-1已经排好序，这时将Ri依次与Ri-1,Ri-2等进行比较，找到应该插入的位置，插入位置及其后的记录依次向后移动。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]第一趟排序从第二个元素3开始和它之前的有序序列比较，3<5,则需要将5向后移动；第二趟排序7>5则直接插入当前位置不用移动其他元素，依次类推每趟排序结果如下:第1趟排序结果: [3, 5, 7, 6, 4, 1, 0, 2, 9, 10, 8]第2趟排序结果: [3, 5, 7, 6, 4, 1, 0, 2, 9, 10, 8]第3趟排序结果: [3, 5, 6, 7, 4, 1, 0, 2, 9, 10, 8]第4趟排序结果: [3, 4, 5, 6, 7, 1, 0, 2, 9, 10, 8]第5趟排序结果: [1, 3, 4, 5, 6, 7, 0, 2, 9, 10, 8]第6趟排序结果: [0, 1, 3, 4, 5, 6, 7, 2, 9, 10, 8]第7趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]第8趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]第9趟排序结果: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8]第10趟排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

/** 插入排序* nums 待排序数组* */public static void insertSort(int[] nums) {int temp = 0;int j;for (int i = 1; i < nums.length; i++) {temp = nums[i]; // 待插入元素for (j = i; j > 0 && temp < nums[j - 1]; j--) { // 寻找插入位置nums[j] = nums[j - 1]; // 插入位置及后元素后移}nums[j] = temp; // 待插入元素放入插入位置}}

希尔排序

希尔排序又称为"缩小增量排序"，它是对直接插入排序方法的改进。

希尔排序的基本思想是先将整个待排序列分割成若干子序列，然后分别进行直接插入排序，待整个排序序列基本有序时，再对全体序列进行一次直接插入排序。过程为先取d1作为第一个增量，把序列分成d1个组，即将所有距离为d1倍数序号的值放在同一组，组内进行直接插入排序；然后取第二个增量d2(d2 < d1)重复上述分组和排序工作，以此类推，直到所取增量di=1（di < di-1 <...< d2 < d1），即所有序列放在同一个组进行直接插入排序为止。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8] 增量序列为 incre[5, 3, 1]第1趟排序时增量为5，原序列分为5组分别是[5,1,8]、[3，0]、[7，2]、[6，9]、[4，10] 对各组分别用直接插入排序得到[1,5,8]、[0,3]、[2,7]、[6,9]、[4,10]然后从各组依次取一个元素合并数组得到第一趟排序结果为:[1, 0, 2, 6, 4, 5, 3, 7, 9, 10, 8]；第2趟排序取第二个增量为3，则分组为[1,6,3,10][0,4,7,8][2,5,9]重复子数组排序并合并得到第2趟排序结果：[1, 0, 2, 3, 4, 5, 6, 7, 9, 10, 8]；最后一趟排序增量为1，即此时数组已相对有序对所有序列进行直接插入排序即可。第1趟排序结果:[1, 0, 2, 6, 4, 5, 3, 7, 9, 10, 8]第2趟排序结果:[1, 0, 2, 3, 4, 5, 6, 7, 9, 10, 8]第3趟排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

/** 希尔排序* nums 待排序数组* incre 增量序列* */public static void shellSort(int[] nums,int[] incre) {int j;for (int i = 0; i < incre.length; i++) { // 从最大增量逐减分组for (int k = incre[i]; k < nums.length; k++) { // 从增量incre[i]向后遍历序列int temp = nums[k];// 序号为incre[i]（增量）倍数的为同一组，进行组内直接插入排序for ( j = k; j >= incre[i] && temp < nums[j - incre[i]] ; j-=incre[i]) {nums[j] = nums[j-incre[i]];}nums[j] = temp;}}}

快速排序

快速排序的基本思想是：通过一趟排序将待排序的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的序列值均不大于后半区中的序列值，然后再对这两部分序列值继续进行快速排序，从而使整个序列有序。一趟快速排序的过程称为一次划分，具体做法是：附设两个位置指示变量i和j，它们的初值分别指向序列的第一个值和最后一个值。设枢纽记录（通常是第一个值）pivot，则首先从j所指位置起向前搜索，找到第一个小于pivot的序列值，并将其向前移到i所指示的位置，然后从i所指示的位置向后搜索，找到第一个大于pivot的序列值将其向后移动到j所指示的位置，重复该过程直到i和j相等为止。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]第一次划分时 取pivot=5,此时i=0，j=10 从右往左找第一个小于pivot的值为2 此时i=0，j=7 将i和j处元素交换位置得到序列：[2, 3, 7, 6, 4, 1, 0, 5, 9, 10, 8]；继续从i=0开始向右找第一个大于pivot的值为7，此时i=2,j=7 交换i、j处元素位置得到序列：[2, 3, 5, 6, 4, 1, 0, 7, 9, 10, 8]；继续从j=7向左找第一个小于5的数为0 此时i=2,j=6 交换i、j处元素位置得到序列：[2, 3, 0, 6, 4, 1, 5, 7, 9, 10, 8]；继续从i=2向右找第一个大于5的数为6 此时 i=3,j=6 交换i、j处元素位置得到序列：[2, 3, 0, 5, 4, 1, 6, 7, 9, 10, 8]；继续从j=6开始向左找第一个小于5的数为1 此时 i=3,j=5 交换i、j处元素位置得到序列：[2, 3, 0, 1, 4, 5, 6, 7, 9, 10, 8]；继续从i=3向右寻找第一个大于5的数为6 此时 i=6,j=6，这时pivot将数组分为前后两个半区，前半区均小于pivot后半区均大于pivot然后对前后两个半区分别进行快速排序。

/** 快速排序一次划分* nums 待划分数组* low 左位置* high 右位置* */public static int divide(int[] nums, int low, int high) {int pivot = nums[low];// 选择第一个元素作为pivotint left = low;int right = high;​while (left < right) {// 从右向左找出比pivot小的数据while (left < right && nums[right] > pivot) {right--;}// 从左向右找出比pivot大的数据while (left < right && nums[left] <= pivot) {left++;}// 没有过界则交换if (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}}// 最终将分界值与当前位置数据交换nums[low] = nums[right];nums[right] = pivot;// 返回分界值所在下标return right; // left 和 right一样}​​​/** 快速排序（有交换法、挖坑法、单边指针法 这里是交换法）* nums 待排序列* low 数组左下标* high 数组右下标* */public static void quickSort(int[] nums, int low, int high) {if (low >= high) {return;}int index = divide(nums, low, high); // 返回一次划分的下标quickSort(nums, 0, index - 1); // 左半区快排quickSort(nums, index + 1, high); // 右半区快排}

归并排序

两路归并就是递归的将序列从中间位置分为两个子序列，直到子序列的元素为一个为止。然后将相邻的两个子序列归并为一个有序序列，不断合并直到原序列全部有序。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]每个序列会先分成两个子序列，子序列再分子序列直到子序列的元素为1个时进行排序并归并。[5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8] ---> [5, 3, 7, 6, 4, 1] 和 [0, 2, 9, 10, 8][5, 3, 7, 6, 4, 1] ---> [5, 3, 7] 和 [6, 4, 1][5, 3, 7] ---> [5, 3] 和 [7][5, 3]---> [5] 和 [3][5] 和 [3]归并排序后为[3,5]再与[5, 3, 7]的右半子序列[7]合并排序得到[3,5,7]依次类推得到最终有序序列。

/** * * * * * *归 并 排 序* * * * * ** nums 需排序数组* l 数组 左下标* h 数组 右下标（非数组长度）* */public static void mergeSort(int[] nums, int l, int h) {​if (l == h) return; // 左等于右 一个元素递归出口int mid = l + (h - l) / 2;// 计算左右分界点mergeSort(nums, l, mid);// 左数据有序mergeSort(nums, mid + 1, h); // 右数据有序int[] newNum = new int[h - l + 1]; // 辅助数据存放左右合并排序后的数据​int m = 0, i = l, j = mid + 1;while (i <= mid && j <= h) {newNum[m++] = nums[i] <= nums[j] ? nums[i++] : nums[j++]; // 左右数组递增排序放入newNum}while (i <= mid) { // 右数组先放完，则把左数组剩余依次放入newNum[m++] = nums[i++];}while (j <= h) {// 左数组先放完，则把右数组剩余依次放入newNum[m++] = nums[j++];}for (int k = 0; k < newNum.length; k++) {nums[l++] = newNum[k]; // 将a[l,...,h]的元素按排序后放回}}

堆排序

对于n个元素的关键字序列{K1,K2,...Kn},当且仅当满足{Ki<=K2i && Ki<=K2i+1}或{Ki>=K2i && Ki>=K2i+1}时，若将此序列对应的一维数组看成一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不小于（或不大于）其左、右孩子结点的值。因此，在一个堆中，堆元素（即完全二叉树的根结点）必为序列中的最大元素（或最小元素），并且堆中的任一棵树也是堆。

堆排序的基本思想是：对一组待排序的序列。首先按堆的定义排成一个序列（建立初始堆），从而可以输出堆顶最大元素，然后将剩余的元素再调整成新堆，得到次大值，如此反复，直到全部元素有序。

初始堆建立方法：根据完全二叉树的特性，所有i>n/2的元素都没有子结点，因此，初始堆的建立可以从完全二叉树的第n/2个结点开始，向元素下标递减的方向调整，逐步使以Kn/2,....K2,K1为根的子树满足堆的定义。

例如 序列： a = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]对于元素4以后的序列元素无孩子结点，故构建初始堆只考虑 [5, 3, 7, 6, 4]因此构建的初始堆为[10, 9, 7, 6, 8, 1, 0, 2, 5, 4, 3]第1趟排序结果: [9, 8, 7, 6, 4, 1, 0, 2, 5, 3, 10]第2趟排序结果: [8, 6, 7, 5, 4, 1, 0, 2, 3, 9, 10]第3趟排序结果: [7, 6, 3, 5, 4, 1, 0, 2, 8, 9, 10]第4趟排序结果: [6, 5, 3, 2, 4, 1, 0, 7, 8, 9, 10]第5趟排序结果: [5, 4, 3, 2, 0, 1, 6, 7, 8, 9, 10]第6趟排序结果: [4, 2, 3, 1, 0, 5, 6, 7, 8, 9, 10]第7趟排序结果: [3, 2, 0, 1, 4, 5, 6, 7, 8, 9, 10]第8趟排序结果: [2, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10]第9趟排序结果: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]第10趟排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

/** 数组元素调整成大根堆*nums 待排序数组* s nums[s..len] 序列元素中，除nums[s]外，其余元素均满足大顶堆定义* len 待排序列的最大下标（非数组长度）* */public static void heapAdjust(int[] nums, int s, int len) {int temp = nums[s]; // 临时备份nums[s] 寻找合适位置插入int i; // i 取值 为数组对应完全二叉树的左孩子结点的值for (i = 2 * s + 1; i <= len; i = i * 2 + 1) { // 沿值较大的孩子结点向下筛选if (i < len && nums[i] < nums[i + 1]) i++; // i 取左孩子和右孩子较大者的下标if (temp >= nums[i]) break; // s 处值满足大顶堆，跳出nums[s] = nums[i]; // 大值插入根结点s = i; // s 记录待插入元素的位置}nums[s] = temp; // 插入备份元素}​​/** * * * * * 堆 排 序 * * * * ** nums 待排序数组* len 数组长度* */public static void heapSort(int[] nums, int len) {for (int i = len / 2 - 1; i >= 0; i--) { // len / 2 - 1 以后的元素无子结点heapAdjust(nums, i, len - 1); // nums[0,....,len-1] 调整为大根堆}for (int i = 1; i < len; i++) {int temp = nums[0];nums[0] = nums[len - i]; // 堆顶元素与序列尾元素交换nums[len - i] = temp;heapAdjust(nums, 0, len - i - 1); // 待排元素-1，将剩余nums[0,...,len-i-1] 元素重新调整为大根堆。}}

基数排序

基数排序的思想是按组成元素的各个数位的值进行排序，它是分配排序的一种。在该排序方法中将一个元素看成一个d元组，即Ki1，Ki2...,Kid;其中 0 <= Kij< r,i =(1 ~ n),j=(1 ~ d)。r称为基数，待排序列为10进制则r=10，待排序列为八进制则r=8。d是序列元素的最大位数，不足d位的在前边补0。基数排序有MSD（最高位优先），和LSD（最低位优先）。

基本思想：设立r个桶，桶的编号为0，1，...r-1。首先按最低有效位的值把n个元素分配到r个桶中；然后按照桶编号从小到大将各桶中的元素收集起来；接着再按次低有效位的值把刚收集的元素再分配到r个桶中，重复上述分配和收集的过程，直到按照最高有效位分配和收集，这样就得到了一个从小到大的有序序列。

例如 序列： a = [5,3,7,6,4,1,0,2,9,10,8,11,21,31,41,52,63,74,84,96,101,201,304]序列a最大元素只有三位数，对于基数排序只需三趟排序从最低有效位 个位起 0号桶元素为[0，10]1号桶为[1,11,21, 31, 41, 101, 201]2号桶为[2, 52]3号桶为[3, 63]4号桶为[4, 74, 84, 304]5号桶为[5]6号桶为[6，96]7号桶为[7]8号桶为[8]9号桶为[9]因此第1趟排序结果:[0,10,1,11,21,31, 41, 101, 201, 2, 52, 3, 63, 4, 74, 84, 304, 5, 6, 96, 7, 8, 9]第二趟从十位起0号桶元素为[0, 1, 101, 201, 2, 3, 4, 304, 5, 6, 7, 8, 9]1号桶为[10, 11]2号桶为[21]3号桶为[31]4号桶为[41]5号桶为[52]6号桶为[63]7号桶为[74]8号桶为[84]9号桶为[96]因此第2趟排序结果:[0,1,101,201,2,3, 4, 304, 5, 6, 7, 8, 9, 10, 11, 21, 31, 41, 52, 63, 74, 84, 96]第三趟从百位起0号桶元素为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 31, 41, 52, 63, 74, 84, 96]1号桶为[101]2号桶为[201]3号桶为[304]其他桶无元素，因此第3趟排序结果:[0,1,2,3,4, 5,6, 7, 8, 9, 10, 11, 21, 31, 41, 52, 63, 74, 84, 96, 101, 201, 304]

/** 基数排序* nums 待排序数组* */public static void radixSort(int[] nums) {int max = nums[0];for (int i = 1; i < nums.length; i++) {if (max<nums[i]) max = nums[i];}int maxLen = (max+"").length(); // 计算数组元素最大位数int[][]bucket = new int[10][nums.length]; //这10个桶按不同的有效位存储有效数字分别为0-9的元素int[]order = new int[10]; //数组order[i]用来表示该有效位是i的元素的个数int k = 0,n = 1,d = 1; //d=1 按照LSD从最低有效位开始while(d <= maxLen) { // 从最低有效位开始一直到最高有效位重复将元素分配到不同的桶for(int i = 0; i < nums.length; i++) {int lsd = ((nums[i] / n) % 10); // 计算有效位数字bucket[lsd][order[lsd]] = nums[i]; // 元素分配到对应桶order[lsd]++;// 对应桶元素个数增加}for(int i = 0; i < 10; i++) {for(int j = 0; order[i] != 0 && j < order[i]; j++) {nums[k] = bucket[i][j]; // 按桶编号将排序元素重新收集bucket[i][j] = 0;k++;}order[i] = 0;// 清0桶元素个数，进高位重新分配}n *= 10;// 10进制每进位乘10k = 0;d++;// 有效位进高1位}}

总结

如果觉得《Java实现常见排序算法》对你有帮助，请点赞、收藏，并留下你的观点哦！