![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cTwqfjEg-1652773993433)(D:\Desktop\Java\imag\排序.png)]](https://img-blog.csdnimg.cn/26391f48669a4be79782a1c84062f8a1.png)
常见排序列表：
package queue;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class Demo3 {
public static void main(String[] args) {
//-----------------------------------------------普通测试
// int[] num = {5,2,6,7,8,10};
// System.out.println("排序前");
// System.out.println(Arrays.toString(num));
// int[] array = bubbleSort(num);
// System.out.println("排序后");
// System.out.println(Arrays.toString(array));
//-----------------------------------------------向数组中添加多个（80000）数据测试排序时间
int[] arr = new int[80000];
for(int i=0;i < 80000;i++) {
arr[i] = (int)(Math.random()*80000);
}
Date time1 = new Date();
//时间格式化
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String timePre = sdf.format(time1);
System.out.println("排序前的时间是:"+timePre);
//调用排序算法
bubbleSort(arr);
Date time2 = new Date();
String timeNex = sdf.format(time2);
System.out.println("排序后的时间是:"+timeNex);
/**
* 由此测试可以看出，冒泡排序的时间复杂度比较高
* 排序前的时间是:2022-03-21 14:47:55
* 排序后的时间是:2022-03-21 14:48:27
* */
}
public static int[] bubbleSort(int[] num) {
boolean flag = true;
int temp=0;
for(int i=0;i < num.length-1;i++) {//或i = num.length-1;i>0;i--
for(int j=0;j < num.length-i-1;j++) {//或j=0;j<i;j++
if(num[j] > num[j+1]) {
flag = false;
temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
// System.out.println("第"+(i+1)+"趟排序结果:");
// System.out.println(Arrays.toString(num));
/**
* 这里的flag判断的作用是，优化时间复杂度
* 当传入一个只需要走两三步就可完成排序的数组时，如：[5,2,6,7,8,10]
* 只需要循环一次就可以得到最终的结果
* */
if(flag) {
break;
}else {
flag = true;//重置flag为true，如果执行到这里说明元素发生过交换。flag已经为false。
}
}
return num;
}
}
思路：每次从后面选择最小的放在当前区间的前面
第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换， 第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换， 第三次从arr[2] arr[n-1]中选取最小值，与arr[2]交换， .，第i次从arr[i-1]' arr[n-1]中选取最小值，与arr[i-1]交换，..第n-1次从arr[n-2]^ arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
代码演示：
package dataStructure;
import java.text.SimpleDateFormat;
//选择排序
import java.util.Arrays;
import java.util.Date;
public class SelectSorting {
public static void main(String[] args) {
//------------------------------------------------普通测试
// int[] arr = {5,8,3,9,10};
// selectSort(arr);
// System.out.println("排序后:"+Arrays.toString(arr));
//------------------------------------------------测试多个数据的时间复杂度
int[] arr = new int[80000];
for(int i=0;i < 80000;i++) {
arr[i] = (int)Math.random()*80000;
}
Date time1 = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");//日期格式化
System.out.println("测试前时间:"+sdf.format(time1));
selectSort(arr);
Date time2 = new Date();
System.out.println("测试后时间:"+sdf.format(time2));
/**
* 测试前时间:2022-03-21 14:46:25
* 测试后时间:2022-03-21 14:46:26
* 同样测试80000个数据，选择排序的时间复杂度要低于冒泡排序
* */
}
public static void selectSort(int[] arr) {
/**
* 算法思想：
* 1.一共需要比较arr.length - 1轮才能得出结果
* 2.每一轮中先使用变量min记录arr[i],index记录i的位置。进入下一层循环中之后
* 如果arr[i] > arr[j]，就用index记录j的位置，min记录arr[j]的值，
* 也就是在整个第二层循环中arr[i]的值和位置就没有发生改变，只有第二层循环完之后，判断index的值是否发生了改变，如果改变了就交换值即可
* 如果条件不满足，则下一次循环
*
* */
for(int i=0;i < arr.length-1;i++) {
int index = i;//辅助下标
int min = arr[i];
//从下标i的后面一个开始比较
for(int j=i+1;j < arr.length;j++) {
if(arr[i] > arr[j]) {
index = j;//重置index
min = arr[j];//重置min
}
}
if(index != i) {
arr[index] = arr[i];
arr[i] = min;
}
}
}
}
以插入一个元素为例：
package dataStructure;
import java.text.SimpleDateFormat;
/**
* 算法思想：
* 1.从数组的第二个数据开始操作（下标为0），因为本算法的思想就是待插入的数据都会一一和前面的数据做比较，所以数组里的第一个数据（因为只有一个）是有序的。
* 这样后面的数据插入的时候前面的数据就是一个有序的列表，和它前面的数据一直比较一直交换位置，直到比较到前面一个比它大的时候为止
* 2.使用insertVal变量来记录当前需要插入的数据；insertIndex变量记录insertVal的前面数据的下标，初始的时候insertIndex位于当前数据的前一个
* 3.限制范围insertIndex >= 0 是合法的，因为insertIndex需要依次遍历insertVal前面的元素，直到第一个元素。防止越界
* 4.还需要同时满足arr[insertIndex] > insertVal。
* 如果满足：当前被比较的（insertIndex位置上的元素）往后移动一位
* 当while循环中执行完毕，此时insertIndex移动到数组下标为0/或insertVal合适大小的位置上来了，此时只需arr[insertIndex + 1] = insertVal即可
* 最后一步为什么是insertIndex+1？因为当前的insertIndex是比较的位置，当前insertIndex这个位置上的元素肯定是小于insertVal的，所以insertVal需要插入在后面一个位置上
*
*
* */
import java.util.Arrays;
import java.util.Date;
public class InsertSorting {
public static void main(String[] args) {
//-----------------------------------------------普通测试
// int[] arr = {90,-2,200,73,-20,3};
// insertSort(arr);
// System.out.println(Arrays.toString(arr));
//------------------------------------------------执行速度测试
int[] arr = new int[80000];
for(int i=0;i < 80000;i++) {
arr[i] = (int)Math.random()*80000;
}
Date time1 = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");
System.out.println("测试前时间:"+sdf.format(time1));
insertSort(arr);
Date time2 = new Date();
System.out.println("测试后时间:"+sdf.format(time2));
/**
* 测试结果：
* 测试前时间:2022-03-21 15:49:46:4946
* 测试后时间:2022-03-21 15:49:46:4946
* 可见：选择排序执行效率非常高
* */
}
public static void insertSort(int[] arr) {
for(int i=1;i < arr.length;i++) {
int insertVal = arr[i];
int insertIndex = i-1;
while(insertIndex >= 0 && arr[insertIndex] > insertVal) {
arr[insertIndex+1] = arr[insertIndex];//数据往后移动一位
insertIndex--;
}
if(insertIndex+1 != i) {//如果不满足此条件，说明需要插入的位置就是i这个位置，就不需要执行下面的代码
arr[insertIndex+1] = insertVal;
}
}
}
}
插入排序存在的问题：
当需要对arr = {2,3,4,5,6,1};这样一个数组进行排序时。可以知道需要插入的数据是1，这个过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
这样后移的次数明显增多，对效率有影响
为了解决这一问题，提高排序效率。引入希尔排序
希尔排序也是一种插入排序，他是简单插入排序改进之后的一个更高效的版本，也称为缩小增量排序
package dataStructure;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class ShallSorting {
public static void main(String[] args) {
//-------------------------------------------------普通测试
// int[] arr = {8,9,1,7,2,3,5,4,6,0};
// shellSort1(arr);
// System.out.println(Arrays.toString(arr));
//-------------------------------------------------执行效率测试
int[] arr = new int[80000];
for(int i=0;i < 80000;i++) {
arr[i] = (int)Math.random()*80000;
}
Date time1 = new Date();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");
System.out.println("测试前时间:"+sdf.format(time1));
//shellSort1(arr);
//测试前时间:2022-03-21 19:30:06:306
//测试后时间:2022-03-21 19:30:18:3018
shellSort2(arr);
//测试前时间:2022-03-21 19:30:49:3049
//测试后时间:2022-03-21 19:30:49:3049
Date time2 = new Date();
System.out.println("测试后时间:"+sdf.format(time2));
}
//方法一：交换法，此方法时间效率不高
public static void shellSort1(int[] arr) {
int temp=0;//元素交换中间值
for(int step = arr.length/2; step > 0;step /= 2) {//step为步长。
for(int i=step;i < arr.length;i++) {
for(int j=i-step;j >= 0;j -= step) {
if(arr[j] > arr[j+step]) {
temp = arr[j];
arr[j] = arr[j+step];
arr[j+step] = temp;
}
}
}
}
}
//方法二：移位法
//
public static void shellSort2(int[] arr) {
//增量step，逐步缩小增量
for(int step = arr.length/2;step > 0;step /=2) {
//从第step个元素，逐个对其所在的组进行插入排序
//以下操作步骤和插入排序类似
for(int i=step;i < arr.length;i++) {
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-step]) {//判断当前元素是否是小于j-step个元素，因为前面已经有序，如果不满足，则无需插入。
while(j-step >= 0 && temp < arr[j-step]) {
arr[j] = arr[j-step];//向后移动这个比temp大的元素
j -= step;
}
//如果执行到这里，说明当前的temp这个元素比前面的一部分或者全部小
//需要将temp值赋给当前j移动到的位置
arr[j] = temp;
}
}
}
}
}
图形分析：
快排就是冒泡排序的升级版本
package dataStructure;
import java.util.Arrays;
import java.util.Random;
/**
* 快速排序法思想：
* 对于给定的一组记录，选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，
* 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好
* 序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到序列中的所有记录均有序为止。
* */
public class QuickSorting {
public static void main(String[] args) {
//-----------------------------------------------------普通测试
// int[] arr = {6,1,2,7,9,3,4,5,10,8};
quickSort(arr,0,arr.length-1);
// quickSort(arr,0,arr.length-1);
// System.out.println(Arrays.toString(arr));
//------------------------------------------------------时间效率测试
int[] arr = new int[100000];
Random r = new Random();
for(int i=0;i<arr.length;i++) {
int num = r.nextInt();
arr[i] = num;
}
long start = System.currentTimeMillis();
// quickSort(arr,0,arr.length-1);
quickSortEasy(arr,0,arr.length - 1);
long end = System.currentTimeMillis();
System.out.println("耗时:"+(end-start)+"ms");
}
/**
* * 方法实现：以中间元素为基准数
* 向方法中传入数组arr，[left,right]区间。可以选择数组下标区间排序。
* 在本方法中我们选择位于left和right中间的元素（pivot：中轴）为基准 pivot = arr[(left+right)/2]
* 传入的left和right不能变，因为后面递归的时候还要使用。所以我们使用两个变量l和r分别保存left和right
* 现在开始遍历[left，right]区间里的元素，只要 l < r 都继续遍历：
* 向基准左边遍历：直到找到一个大于等于基准的元素，即：arr[l] >= pivot;本次遍历结束，l++;
* 向基准右边遍历：直到找到一个小于基准的元素，即 arr[r] < pivot;本次遍历结束r--;
* 将找到的左边大于等基准的元素与右边小于基准的元素交换位置
* */
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;//用于交换的中间变量
//while循环的目的就是让比pivot值小的放在基准左边，比基准大的放在右边
while(l < r) {
//找左边，一直找到大于等于pivot的值才退出
while(arr[l] < pivot) {
l += 1;
}
//找右边，一直找到小于等于pivot的值，才退出
while(arr[r] > pivot) {
r -= 1;
}
//这里说明pivot左边都小于等于他，右边都大于等于他
//此时就可以退出最外层while循环了
if(l >= r) break;
//不满足l >= r的条件，交换上面两个while循环找到的值
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完之后，发现arr[l] == pivot相等，则r--，往前移
if(arr[l] == pivot) r -= 1;
//如果交换完之后，发现arr[r] == pivot相等，则l++，往后移
if(arr[r] == pivot) l += 1;
}
//如果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);
}
}
//------------------------------------------------------------------------------------
/**
* 以第一个元素为基准数
* */
public static void quickSortEasy(int[] arr,int left,int right) {
if(left > right) {
return;
}
//变量base保存基准数
int base = arr[left];
//变量l指向最左边
int l = left;
//变量r指向最右边
int r = right;
while(l != r) {//当l和r不相遇时就一直遍历
//r向左遍历，直到找到小于基准数的，暂停。如果遍历到大于等于基准数的，就继续遍历
while(arr[r] >= base && l < r) {
r--;
}
//l从左往右遍历
while(arr[l] <= base && l < r) {
l++;
}
//如果到这里说明l，r都停下了，交换l和r位置上的元素
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
/**
* 如果while(l != r)不成立了，就跳出上面的循环，往下执行。此时说明l和r相遇了
* 如果l和r相遇，此时就交换基准数与l，r相遇位置上的元素
* */
arr[left] = arr[l];//这里arr[l]和arr[r]是同一个元素
arr[l] = base;
/**
* 到这里，第一轮基准数就回到它自己的位置上了（左边都小于它，右边都大于等于它）
* */
//排基准数的左边
quickSortEasy(arr,left,l - 1);
//排基准数的右边
quickSortEasy(arr,r + 1,right);
}
}
图片演示例子：
算法思想：分治
package dataStructure;
import java.util.Arrays;
import java.util.Random;
public class MergeSorting {
public static void main(String[] args) {
//---------------------------------------------------普通测试
// int[] arr = {10,6,7,1,3,9,4,2};
// merge(arr,0,arr.length-1);
// System.out.println(Arrays.toString(arr));
//---------------------------------------------------时间复杂度测试
//耗时:44ms
int[] arr = new int[100000];
Random r = new Random();
for(int i=0;i<arr.length;i++) {
int num = r.nextInt();
arr[i] = num;
}
long start = System.currentTimeMillis();
merge(arr,0,arr.length-1);
long end = System.currentTimeMillis();
System.out.println("耗时:"+(end-start)+"ms");
}
//分组：
public static void merge(int[] arr,int left,int right) {
if(left >= right) {//当left和right相遇的时候，说明元素分组完毕
return;
}
int mid = (left+right)>>>1;//无符号右移一位
merge(arr,left,mid);//左边分组
merge(arr,mid+1,right);//右边分组
//分组完毕之后，就开始归并了
megerSort(arr,left,mid,right);
}
//归并
public static void megerSort(int[] arr,int left,int mid,int right) {
int s1 = left;//当前分区的初始索引
int s2 = mid+1;//mid右边分区的初始索引
int[] temp = new int[right-left+1];//用于临时存储归并数据的数组
int k = 0;//temp数组的初始索引
//1.把左右两边有序的数据按照规则填充到temp数组
//直到左右两边的有序序列有一边处理完毕为止
while(s1 <= mid && s2 <= right) {
if(arr[s1] <= arr[s2]) {
temp[k++] = arr[s1++];
}else {
temp[k++] = arr[s2++];
}
}
//2.把上边处理剩下的数据全部填充到temp（剩下的只能是一边的，而且是有序的）
while(s1 <= mid) {//如果是左边剩
temp[k++] = arr[s1++];
}
while(s2 <= right) {//如果是右边剩
temp[k++] = arr[s2++];
}
//3.将temp中的数据拷贝到arr中
for(int i = 0;i < temp.length;i++) {
arr[i+left] = temp[i];
}
}
}
又称桶排序，是一种稳定的排序算法.使用内存换时间的经典算法，它对空间的要求比较高，
基本思想：
将所有待比较数值统一为同样的数位长度， 数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直 到最高位排序完成以后,数列就变成一个有序序列。
图文说明：
代码块：
package dataStructure.sort;
import java.util.Arrays;
//基数排序，又称桶排序
public class BucketSorting {
public static void main(String[] args) {
int[] arr = {53,3,5424,888,126,90};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
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 len = (max + "").length();
//开始循环
for(int i=0,n=1;i < len;i++,n *= 10) {
//声明十个一维数组作为桶，放入二维数组
//第二维长度为arr.length的原因是，为防止空间浪费，当每数组个数据模除结果都相同时放入同一个桶内
//这个时候最大
int[][] bucket = new int[10][arr.length];
//此数组用于存放每次循环过程中，每一个桶内存放了多少个有效数据
int[] bucketElementCounts = new int[10];
for(int j=0;j < arr.length;j++) {
/**
* n:第一轮需要求arr[j]的个位，所以n=1
* 第二轮需要求十位，所以n=10
* 。。。。
* */
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];
}
}
}
}
}
}
堆在结构上就是一棵完全二叉树。只是在完全二叉树的基础上有些要求：
大顶堆：每一个树结点的值都大于等于其左右子结点的值，没有规定左右子结点大小规则。（每一棵子树中最大值都是根结点）
小顶堆：每一个树结点的值都小于等于其左右子结点的值。
堆排序一般升序采用大顶堆，降序采用小顶堆
思路：
1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆；
2.将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端
3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
代码演示：图文演示：https://www.yuque.com/dubucahaojiusandianban/dfiuh9/qz5fd8/edit，“堆排序”
public class HeapSort {
public static void main(String[] args) {
int[] arr = {20,8,25,10,6,9,30,50,11,80};
heapSort(arr);
}
//堆排序处理
//交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区，然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置......
public static void heapSort(int[] arr) {
int temp = 0;
//----------------------------1.将无序序列构建成一个堆
//arr.length/2-1得到非叶子结点的个数
for(int i=arr.length/2-1;i >= 0;i--) {
//从第一个非叶子结点从下至上，从左至右进行大顶堆调整
adjustHeap(arr,i,arr.length);
}
//-----------------------------2.调整结构+交换堆顶元素与末尾元素。
//最后一个元素不用再调整大顶堆了，所以临界条件是j > 0
for(int j=arr.length-1;j > 0;j--) {
//交换第一个和第j个元素
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);//这里传入的adjustHeap(arr,i,length)的参数i是0，说明到第一次交换头尾元素之后，后面的大顶堆结构调整都是从根结点开始调整
}
System.out.println(Arrays.toString(arr));
}
/**
* 功能：完成将以i对应的非叶子结点的树调整成大顶堆，（仅是调整过程，建立在大顶堆已构建的基础上）
* arr待调整的数组
* i表示非叶子结点在数组中索引
* length表示对多少个元素继续调整，length是逐渐减少的
* */
public static void adjustHeap(int[] arr,int i,int length) {
int temp = arr[i];//临时保存当前元素的值
//开始调整
//n = n*i+1是i结点的左子结点
for(int n = i*2+1;n < length;n = n*2+1) {//从i结点的左子结点开始
if(n+1 < length && arr[n] < arr[n+1]) {//说明左子结点小于右子结点
n++;//n++之后n变成右子结点对应的数组索引
}
if(arr[n] > temp) {//如果子结点大于父节点
arr[i] = arr[n];//把较大的子结点的值赋值给父结点
i = n;//此时又把较大的子结点当做父结点，继续比较
}else {
break;//如果两个子结点都没有大于父结点的（满足大顶堆的要求），就退出循环。
}
}
//for循环结束后，需要将temp值放到调整后的位置。这里的i可能变化（当左右子结点有大于父结点的时候，i就会变化）
//就算i没有变化，还是传值进来的那个i，赋值也不会产生影响
arr[i] = temp;
}
}