JAVA排序

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

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

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

常见算法排序：

交换排序

1.快速排序

快速排序（QuickSort）的基本思路：

1.选出一个数据（一般是最左边或是最右边的）存放在temp变量中，在该数据位置形成一个坑
2、还是定义一个l和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

图解：

代码详解

// 分区方法
public static int Partition(int[] arr, int low, int high) {int pivot = arr[low]; // 选择第一个元素作为基准while (low < high) {// 从右边寻找小于基准的元素while (low < high && arr[high] >= pivot) {high--;}arr[low] = arr[high]; // 将小于基准的元素移动到左边// 从左边寻找大于基准的元素while (low < high && arr[low] < pivot) {low++;}arr[high] = arr[low]; // 将大于基准的元素移动到右边}arr[low] = pivot; // 将基准放到正确的位置return low; // 返回基准位置
}// 快速排序方法public static void QuickSort(int[] arr, int low, int high) {if (low < high) {int pivot = Partition(arr, low, high); // 获取基准位置QuickSort(arr, low, pivot - 1); // 递归处理左侧QuickSort(arr, pivot + 1, high); // 递归处理右侧}}public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] arr=new int[5];
for(int i=0;i<5;i++){System.out.println("请输入数字"+(i+1));arr[i]=scan.nextInt();
}
//bubblesort(arr);//System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));//insertSort(arr);//System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));QuickSort(arr, 0, arr.length - 1); // 调用快速排序System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));
}

low < high 在最外层的 if 语句中已经进行了限制，但在 Partition 方法内部仍然需要再次检查。这是因为：

while 循环的条件：在 Partition 方法的两个 while 循环中，low 和 high 指针可能会相遇或交叉。如果不在每次循环的条件中再进行检查，可能会导致在交换元素时越界。例如，当 low 和 high 相等时，继续访问 arr[high] 或 arr[low] 可能会引发错误。

防止不必要的比较：即使外层的 if (low < high) 已经限制了大范围的情况，但在 while 循环中，我们需要确保在任何时刻，low 和 high 的值都是有效的。

时间复杂度平均：O(N^LogN)
空间复杂度：O(LogN)

方法二：前后指针法

方法思路：开始时，prev指针指向序列开头，

cur指针指向prev指针的后一个位置

private static int partition(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}

2.冒泡排序(BubbleSort)：

冒泡排序（BubbleSort）的基本思路：

通过对待排序从前往后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动，较小的往上挪动，就像水底下的气泡一样逐渐向上冒。

图解：

import java.util.Arrays;
import java.util.Scanner;
public class BubbleSort {public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] arr=new int[5];
for(int i=0;i<5;i++){System.out.println("请输入数字"+(i+1));arr[i]=scan.nextInt();
}
bubblesort(arr);System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));
}
public static void bubblesort(int[] arr){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]){int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}System.out.println("第"+(i+1)+"趟排序后的数组");System.out.println(Arrays.toString(arr));}
}
}

运行结果：

2.1.冒泡排序优化

如果有一此没有交换数字，哪说明冒泡排序已结束，可提前结束程序

方法：

使用flag,初始为true,只要进行排序就赋值为false

之后进行判断，若flag为false，则说明发生过排序，继续进行，并把flag再次初始化为true

若flag为true,则说明没发生过排序，停止程序；

import java.util.Arrays;
import java.util.Scanner;
public class BubbleSort {public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] arr=new int[5];
for(int i=0;i<5;i++){System.out.println("请输入数字"+(i+1));arr[i]=scan.nextInt();
}
bubblesort(arr);System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));
}
public static void bubblesort(int[] arr){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]){int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}System.out.println("第"+(i+1)+"趟排序后的数组");System.out.println(Arrays.toString(arr));}
}
}

时间复杂度：最坏情况：O(N^2)
最好情况：O(N)
空间复杂度：O(1)

插入排序

1.直接插入排序

（如果当前一组数据处于有序状态，那最好用的方法是插入排序）

插入排序（InsertSort）基本思路：

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

public static void insertSort(int[] arr){for(int i=1;i<arr.length;i++){int temp=arr[i];int j=i-1;for(;j>=0;j--){if(arr[j]>temp){arr[j+1]=arr[j];}else{break;}}arr[j+1] =temp;System.out.println("第"+(i+1)+"趟排序后的数组"+Arrays.toString(arr));}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] arr=new int[5];
for(int i=0;i<5;i++){System.out.println("请输入数字"+(i+1));arr[i]=scan.nextInt();
}
//bubblesort(arr);//System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));insertSort(arr);System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));
}

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)

2.希尔排序

与直接插入排序类似，是先分组后直接插入排序，分组时多次分组，逐渐从增大每组元素的个数，最后到所有元素都排序；

静态图解：

代码详解：

public static void insertSort(int[] arr,int gap){for(int i=gap;i<arr.length;i++){int temp=arr[i];int j=i-gap;for(;j>=0;j-=gap){if(arr[j]>temp){arr[j+gap]=arr[j];}else{break;}}arr[j+gap] =temp;System.out.println("第"+(i+1)+"趟排序后的数组"+Arrays.toString(arr));}public static void ShellSort(int[] array){
int gap=array.length;
while(gap>1){
gap/2;
shell(arr,gap);}
}public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] arr=new int[5];
for(int i=0;i<5;i++){System.out.println("请输入数字"+(i+1));arr[i]=scan.nextInt();
}
//bubblesort(arr);//System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));insertSort(arr);System.out.println("请输出最后排序好的数组"+Arrays.toString(arr));}

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

选择排序

1.简单选择排序（SelectSort）

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

简单选择排序（SelectSort）的基本思路：

1.选择开头的数为最小数

2.一共遍历arr.length-1次，内层遍历arr.length，如果找到更小的数，就更新最小数和最小数的位置

3.当遍历到数组的最后时，就得到本轮最小数和下标

4.交换

图解

import java.util.*;
public class SelectSort {//selectsort排序的方法、public static void selectSort(int[] arr){for(int i=0;i<arr.length-1;i++){int minIdex=i;//设第一个数为最小，同时将其索引（在数组中的位置）用minIndex表示int min=arr[i];//用min记录最小的数for(int j=i+1;j<arr.length;j++){if(min>arr[j]){min=arr[j];//通过选择将最小的数选出，然后更新min和minIndexminIdex=j;}}arr[minIdex]=arr[i];//将当前位置的数和最小数交换arr[i]=min;System.out.println("这是第"+i+"次排序，结果是：");//记录排序的过程System.out.println(Arrays.toString(arr));}}
//测试排序public static void main(String[] args){Scanner sc=new Scanner(System.in);int[] arr=new int[5];System.out.println("请输入你要排序的数组：");for(int i=0;i<5;i++){arr[i]=sc.nextInt();}selectSort(arr);System.out.println("排序好后的数组是:");for(int i=0;i<5;i++){System.out.print(arr[i]+" ");}}
}

时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)

2.堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。 需要注意的是排升序要建大堆，排降序建小堆。

转载自：https://blog.csdn.net/Javascript_tsj/article/details/124051388

堆排序的基本思想是:

1)将待排序序列构造成一个大顶堆
2)此时，整个序列的最大值就是堆顶的根节点。
3)将其与末尾元素进行交换，此时末尾就为最大值。
4)然后将剩余n-1 个元素重新构造成-一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

图解：


import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int arr[] = {4, 6, 8, 5, 9};System.out.println("排序前" + Arrays.toString(arr));heapSort(arr);System.out.println("排序后" + Arrays.toString(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);}/*** 将堆项元素与末尾元素交换，将最大元素"沉"到数组末端;* 重新调整结构，使其满足堆定义，然后继续交换堆项元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。*/for (int j = arr.length - 1; j > 0; j--) {temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr, 0, j);}}/*** 将一个数组（二叉树）调整成一个大根堆* 功能：完成将以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];//先取出当前元素的值，保存在临时变量//开始调整.//说明:k=i*2+1k是i结点的左子结点for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {if (k + 1 < length && arr[k] < arr[k + 1]) {k++;}if (arr[k] > arr[i]) {arr[i] = arr[k];i = k;} else {break;}}arr[i] = temp;} }

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

归并排序

归并排序（MergetSort）基本思路：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

图解：

图解

代码

import java.util.Arrays;public class MergetSort {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); // 右递归merge(arr, left, mid, right, temp); // 合并}}public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 左边的指针int j = mid + 1; // 右边的指针int t = 0; // temp数组的指针// 填充temp数组while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} else {temp[t++] = arr[j++];}}// 处理剩余元素while (i <= mid) {temp[t++] = arr[i++];}while (j <= right) {temp[t++] = arr[j++];}// 将temp中的元素拷贝回原数组t = 0;int tempLeft = left;while (tempLeft <= right) {arr[tempLeft++] = temp[t++];}}public static void main(String[] args) {int[] arr = {56, 78, 13, 78, 33};int[] temp = new int[arr.length];System.out.println("排序前：" + Arrays.toString(arr));mergeSort(arr, 0, arr.length - 1, temp);System.out.println("排序后：" + Arrays.toString(arr));}
}

基数排序

基数排序（RadixSort）基本思路：

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

import java.util.Scanner;public class RadixSort {public static void radixSort(int[] arr) {// 找到数组中的最大值int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}// 得到最大值的位数int maxLength = (max + "").length();// 初始化桶int[][] bucket = new int[10][arr.length]; // 十个桶int[] bucketElementCounts = new int[10]; // 每个桶中元素的计数// 对每一位进行排序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++) {if (bucketElementCounts[k] != 0) {for (int l = 0; l < bucketElementCounts[k]; l++) {arr[index++] = bucket[k][l];}}bucketElementCounts[k] = 0; // 清空桶的计数}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.print("请输入你要排序的数组的长度: ");int n = sc.nextInt(); // 用户输入数组长度int[] arr = new int[n];System.out.println("请输入" + n + "个整数（用空格分隔）:");for (int i = 0; i < n; i++) {arr[i] = sc.nextInt(); // 用户输入数组元素}radixSort(arr); // 调用基数排序System.out.println("排序好后的数组是:");for (int i = 0; i < n; i++) {System.out.print(arr[i] + " "); // 输出排序后的数组}}
}