所谓排序，就是将一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的 *** 作。排序算法，就是如何使得记录按照要求排列的方法。常用的排序算法大致有8种：插入排序（直接插入排序、希尔排序）、选择排序（简单选择排序、堆排序）、交换排序（冒泡排序、快速排序）、归并排序、基数排序。
一、直接插入排序
算法思想：把要排序的数组分为了两个部分，一部分是排序好的元素，另一部分是待插入的元素，如果选择的元素比已排序好的元素小，则交换，直到全部元素都比较过为止。
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
insertSort(arr);
}
public static void insertSort(int[] arr) {
//第一个元素 默认有序
for (int i = 1; i < arr.length; i++) {
//从第二个元素开始
int temp = arr[i];
for (int j = i; j >= 0; j--) {
//若当前元素不是第一个 并且 当前元素大于temp，则向后移动
if (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
} else {
arr[j] = temp;
break;
}
}
System.out.println(Arrays.toString(arr));
}
}
执行结果：
[5, 10, 12, 13, 7, 4, 2, 15, 9] [5, 10, 12, 13, 7, 4, 2, 15, 9] [5, 10, 12, 13, 7, 4, 2, 15, 9] [5, 7, 10, 12, 13, 4, 2, 15, 9] [4, 5, 7, 10, 12, 13, 2, 15, 9] [2, 4, 5, 7, 10, 12, 13, 15, 9] [2, 4, 5, 7, 10, 12, 13, 15, 9] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：最好情况O(n)，最坏情况O(n²)，平均复杂度O(n²)
空间复杂度：只有temp一个空间，O(1)
二、希尔排序
算法思想：先将整个待排序的序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对所有元素进行直接插入排序。
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
shellSort(arr);
}
public static void shellSort(int[] arr) {
//找到步长
int step = arr.length / 2;
//步长大于0 当步长等于1时，相当于一次直接插入排序
while (step > 0) {
//每个序列都从第二个开始 现在是对每个序列分别进行直接插入排序
for (int i = step; i < arr.length; i++) {
//若第i个元素大于i-step元素，直接插入。小于的话，移动有序表后插入 这个if可以省略
if (arr[i] < arr[i - step]) {
//上一个元素的位置
int j = i - step;
//临时存储当前元素
int temp = arr[i];
//元素后移
arr[i] = arr[i - step];
//找到元素存储的位置j + step
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j = j - step;
}
arr[j + step] = temp;
}
}
step = step / 2;
System.out.println(Arrays.toString(arr));
}
}
执行结果：
[7, 4, 2, 13, 9, 5, 12, 15, 10] [2, 4, 7, 5, 9, 13, 10, 15, 12] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：
最好情况O(nlogn)，最坏情况O(n²)，平均复杂度O(n^1.5)
空间复杂度：只有temp一个空间，O(1)
三、简单选择排序
算法思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
selectSort(arr);
}
public static void selectSort(int[] arr) {
//每次从剩下的元素中选择最小值放到第一个位置
for (int i = 0; i < arr.length - 1; i++) {
//记录每一趟最小值坐标
int min = i;
//寻找每一趟的最小值 先找到坐标 最后再进行交换 减少交换次数
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//元素交换
if (min != i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
执行结果：
[2, 5, 12, 13, 7, 4, 10, 15, 9] [2, 4, 12, 13, 7, 5, 10, 15, 9] [2, 4, 5, 13, 7, 12, 10, 15, 9] [2, 4, 5, 7, 13, 12, 10, 15, 9] [2, 4, 5, 7, 9, 12, 10, 15, 13] [2, 4, 5, 7, 9, 10, 12, 15, 13] [2, 4, 5, 7, 9, 10, 12, 15, 13] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：最好情况O(n²)，最坏情况O(n²)，平均复杂度O(n²)
空间复杂度：只有temp一个空间，O(1)
Tips：选择排序可以进行改进，每次不光找到最大值，还可以找到最小值放到最后，从而减少一半的趟数。
四、堆排序
堆的定义如下：n个元素的序列{k1,k2,···,kn}，当且仅当满足下关系时，称之为堆：
ki <= k(2i) 或 ki >= k(2i)
ki <= k(2i+1) 或 ki >= k(2i+1)
按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值
算法思想：
①创建最小堆：将堆所有数据重新排序
②最大堆调整：将堆的末端子节点作调整，使得子节点永远大于父节点
③堆排序：移除位在第一个数据的根节点，并做最小堆调整的递归运算
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
heapSort(arr);
}
public static void heapSort(int[] arr) {
//初始堆
buildHeap(arr, arr.length);
//从最后一个元素开始对序列进行调整
System.out.println("堆排序开始");
for (int i = arr.length - 1; i > 0; i--) {
//交换堆顶元素arr[0]和堆中最后一个元素
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//每次交换堆顶元素和堆中最后一个元素之后，都要对堆顶进行调整
adjustHeap(arr, 0, i);
}
System.out.println("堆排序结束");
}
private static void buildHeap(int[] arr, int len) {
System.out.println("构建堆开始");
for (int i = (len - 1) / 2; i >= 0; i--) {
adjustHeap(arr, i, len);
}
System.out.println("构建堆结束");
}
执行结果：
构建堆开始 [10, 5, 12, 13, 7, 4, 2, 15, 9] [10, 5, 12, 9, 7, 4, 2, 15, 13] [10, 5, 2, 9, 7, 4, 12, 15, 13] [10, 5, 2, 9, 7, 4, 12, 15, 13] [2, 5, 4, 9, 7, 10, 12, 15, 13] 构建堆结束 堆排序开始 [4, 5, 10, 9, 7, 13, 12, 15, 2] [5, 7, 10, 9, 15, 13, 12, 4, 2] [7, 9, 10, 12, 15, 13, 5, 4, 2] [9, 12, 10, 13, 15, 7, 5, 4, 2] [10, 12, 15, 13, 9, 7, 5, 4, 2] [12, 13, 15, 10, 9, 7, 5, 4, 2] [13, 15, 12, 10, 9, 7, 5, 4, 2] [15, 13, 12, 10, 9, 7, 5, 4, 2] 堆排序结束
Tips：最小堆输出的是倒序，正序排列可构建最大堆
时间复杂度：
最好情况O(nlogn)，最坏情况O(nlogn)，平均复杂度O(nlogn)
空间复杂度：只有temp一个空间，O(1)
五、冒泡排序
算法思想：在要排序的序列中，对当前还未排好序的全部元素，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒，就好像水泡上浮一样，如果他们的顺序错误就把他们交换过来。
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
bubbleSort(arr);
}
public static void bubbleSort(int[] arr) {
//外层循环控制趟数
for (int i = arr.length - 1; i > 0; i--) {
//节点比较 只比较到第i个元素即可
for (int j = 0; j < i; j++) {
//交换元素
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}
执行结果：
[5, 10, 12, 7, 4, 2, 13, 9, 15] [5, 10, 7, 4, 2, 12, 9, 13, 15] [5, 7, 4, 2, 10, 9, 12, 13, 15] [5, 4, 2, 7, 9, 10, 12, 13, 15] [4, 2, 5, 7, 9, 10, 12, 13, 15] [2, 4, 5, 7, 9, 10, 12, 13, 15] [2, 4, 5, 7, 9, 10, 12, 13, 15] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：最好情况O(n)，最坏情况O(n²)，平均复杂度O(n²)
空间复杂度：只有temp一个空间，O(1)
Tips：我们可以看到最后几趟都是没有必要的，因此可以在没有元素交换时中止排序，从而减少循环比较时间。
六、快速排序
算法思想：选择一个基准，通过一趟排序将待排元素分为两个部分，其中一部分比基准值都大，另一部分比基准值都小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。（分而治之的思想）
排序过程：
此时的基准10找到了自己的位置。然后以此类推，递归的排序左序列和右序列即可使整个序列有序。
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int low, int high) {
//递归的中止条件
if (arr.length <= 0) {
return;
}
//递归的中止条件
if (low >= high) {
return;
}
int left = low;
int right = high;
//基准 以序列的第一个元素为基准
int temp = arr[left];
while (left < right) {
//从右侧找到比基准小的
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right];
//从左侧找到比基准大的
while (left < right && arr[left] <= temp) {
left++;
}
arr[right] = arr[left];
}
//放入基准值
arr[left] = temp;
System.out.println(Arrays.toString(arr));
//递归排序左序列
quickSort(arr, low, left - 1);
//递归排序右序列
quickSort(arr, left + 1, high);
}
执行结果：
[9, 5, 2, 4, 7, 10, 13, 15, 12] [7, 5, 2, 4, 9, 10, 13, 15, 12] [4, 5, 2, 7, 9, 10, 13, 15, 12] [2, 4, 5, 7, 9, 10, 13, 15, 12] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：最好情况O(nlogn)，最坏情况O(n²)，平均复杂度O(nlogn)
空间复杂度：最好情况O(logn)，最差情况O(n)
七、归并排序
算法思想：归并排序是将两个（或两个以上）有序序列合并成一个新的有序序列，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
排序过程：
Tips：图中只是为了方便做了向下移动，实际上没有重新复制一个一模一样的数组。
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
mergeSort(arr);
}
public static int[] mergeSort(int[] arr) {
if (arr.length == 1) {
return arr;
}
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
System.out.println("合并：" + Arrays.toString(left) + "t" + Arrays.toString(right));
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right) {
//合并后的数组大小
int[] mergeArr = new int[left.length + right.length];
//i是left坐标，j是right坐标，k是新数组坐标
int i = 0, j = 0, k = 0;
//下边是合并两个有序数组 此时传进来的数组left和right一定是有序的
while (i < left.length && j < right.length) {
mergeArr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
}
//合并left数组剩下的元素
while (i < left.length) {
mergeArr[k++] = left[i++];
}
//合并right数组剩下的元素
while (j < right.length) {
mergeArr[k++] = right[j++];
}
System.out.println(Arrays.toString(mergeArr));
return mergeArr;
}
执行结果：
合并：[10, 5, 12, 13] [7, 4, 2, 15, 9] 合并：[10, 5] [12, 13] 合并：[10] [5] [5, 10] 合并：[12] [13] [12, 13] [5, 10, 12, 13] 合并：[7, 4] [2, 15, 9] 合并：[7] [4] [4, 7] 合并：[2] [15, 9] 合并：[15] [9] [9, 15] [2, 9, 15] [2, 4, 7, 9, 15] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：最好情况O(nlogn)，最坏情况O(nlogn)，平均复杂度O(nlogn)
空间复杂度：O(n)
八、基数排序
算法思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，序列就变成一个有序序列。
排序过程：
代码实现：
public static void main(String[] args) {
int[] arr = new int[]{10, 5, 12, 13, 7, 4, 2, 15, 9};
radixSort(arr);
}
public static void radixSort(int[] arr) {
if (arr.length == 1) {
return;
}
//找到数组中的最大值
int max = 0;
for (int item : arr) {
if (max < item) {
max = item;
}
}
//获取最大位数
int maxDigit = 1;
while (max / 10 > 0) {
maxDigit++;
max = max / 10;
}
//申请桶空间
int[][] buckets = new int[10][arr.length];
int divisor = 10;
for (int i = 0; i < maxDigit; i++) {
//只有10个数字 key是每个位置的值 value存放该值的个数
int[] bucketLength = new int[10];
//分配：将所有元素分配到桶中
for (int value : arr) {
int whereBucket = (value % divisor) / (divisor / 10);
buckets[whereBucket][bucketLength[whereBucket]] = value;
//该位的个数
bucketLength[whereBucket]++;
}
//收集：将不同桶里数据拿出来
int k = 0;
for (int j = 0; j < buckets.length; j++) {
for (int l = 0; l < bucketLength[j]; l++) {
arr[k++] = buckets[j][l];
}
}
System.out.println(Arrays.toString(arr));
divisor = divisor * 10;
}
}
执行结果：
[10, 12, 2, 13, 4, 5, 15, 7, 9] [2, 4, 5, 7, 9, 10, 12, 13, 15]
时间复杂度：d：位数，r：基数，n：序列个数
最好情况O(d*(n+r))，最坏情况O(d*(n+r))，平均复杂度O(d*(n+r))
空间复杂度：O(n+r)
今天的分享就到此结束啦，喜欢的小伙伴记得点赞呦。
关注公众号JavaGrowUp，下期不迷路，获取更多精彩内容。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）