🌍排序的相关概念：
1 排序：
就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2 稳定性：
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
例如：
🌎插入排序
插入排序的核心思想就是把数组中的第一个数据是作为有序的，从第二个数据开始，就要与前面的数据进行比较，在合适的位置进行插入；
代码如下：
public class TestSort { public static void main(String[] args) { int[] array = {12,23,43,52,24,64,78,0,1,4}; InsertSort(array); System.out.println(Arrays.toString(array)); } /** *时间复杂度：O(N^2) 最好情况下O(N) * 空间复杂度：O(1) * 稳定性：稳定 * @param array 待排序数组 */ public static void InsertSort(int[] array){ for (int i = 1; i <array.length ; i++) { //取出当前要进行比较的数据 int tmp = array[i]; //需要从i与前面的数据比较，就从最近的i-1开始 int j = i-1; //j要大于等于零 for (;j>=0;j--){ //如果j位置上数据大于tmp，那么就需要将j+1上的数据覆盖成j位置上的数据 if(array[j]>tmp){ array[j+1]=array[j]; }else{ //说明此时数据是有序的，直接退出循环 break; } } //将tmp放在j+1位置上 array[j+1]=tmp; } } }
**特点:**时间复杂度为O(N)是在数据有序的情况下，所以对于插入排序而言，数据越有序就越快！
🌏 希尔排序
希尔排序其实就是在插入排序的基础上，进行了优化，它所利用的也是直接插入排序，但是它采用了数据分组的思想，接下来就简单的来了解一下什么是希尔排序！
代码如下：
public class TestSort { public static void main(String[] args) { int[] array = {12,23,43,52,24,64,78,0,1,4}; ShellSort(array); System.out.println(Arrays.toString(array)); } //交换元素位置 public static void Swap(int[] array,int i,int j){ int tmp = array[i]; array[i]=array[j]; array[j]=tmp; } /** * 时间复杂度：0(N^1.3)~O(N^1.5) * 空间复杂度：O(1) * 稳定性：不稳定 * @param array 待排序序列 */ public static void ShellSort(int[] array){ int gap = array.length; while(gap!=1){ Shell(array,gap); gap=gap/2; } Shell(array,1); } //插入排序 public static void Shell(int[] array,int gap){ for(int i=gap;i<array.length;i++){ int tmp = array[i]; int j = i-gap; for (;j>=0;j-=gap){ if(array[j]>tmp){ array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } } }
🌳 选择排序
选择排序其实就是，每一次都要将数组中，最小的元素放置到第一位
代码如下：
public class TestSort { public static void main(String[] args) { int[] array = {12,23,43,52,24,64,78,0,1,4}; selection(array); System.out.println(Arrays.toString(array)); } //交换元素位置 public static void Swap(int[] array,int i,int j){ int tmp = array[i]; array[i]=array[j]; array[j]=tmp; } /** * 时间复杂度：O(N^2) * 空间复杂度：O(1) * 稳定性：不稳定 * @param array 待排序数组 */ public static void selection(int[] array){ for(int i = 0;i<array.length;i++){ int minIndex = i;//假设最小值下标一开始是i for(int j = i+1;j<array.length;j++){ if(array[minIndex]>array[j]){ minIndex=j;//找到最小值小标 } } //如果不是i所在位置元素是最小，那么就要交换元素 if(minIndex!=i){ Swap(array,i,minIndex); } } } }
对于选择排序而言，无论数组是否有序，时间复杂度都为O（N^2）!
🍀 堆排序
堆排序就是就是我们之前讲过堆的调整。
代码如下：
public class TestSort { public static void main(String[] args) { int[] array = {12,23,43,52,24,64,78,0,1,4}; HeapSort(array); System.out.println(Arrays.toString(array)); } //交换元素位置 public static void Swap(int[] array,int i,int j){ int tmp = array[i]; array[i]=array[j]; array[j]=tmp; } /** * 时间复杂度：O(N*logN) * 空间复杂度：O(1) * 稳定性：不稳定 * @param array 待排序数组 */ public static void HeapSort(int[] array){ //调整建大堆 for(int parent = (array.length-1-1)/2;parent>=0;parent--){ shiftDown(array,parent,array.length); } //开始排序 int end = array.length-1; while (end>0){ //将最大的放到最后 Swap(array,0,end); end--; //除去最大的之后，堆重新调整,对0位置调整 shiftDown(array,0,end); } } public static void shiftDown(int[] array,int parent,int len){ int child = 2*parent+1; while (child<len){ //找到左右节点的最大值 if(child+1<len&&array[child]<array[child+1]){ child++; } if(array[child]>array[parent]){ Swap(array,parent,child); parent=child; child=2*parent+1; }else{ break; } } } }
🌱 冒泡排序
冒泡排序的时间复杂度：O(N^2)
空间复杂度：O（1）
稳定性：稳定
