排序算法漫游：从冒泡到堆排的底层逻辑与性能厮杀

各位看官早安午安晚安呀

如果您觉得这篇文章对您有帮助的话

欢迎您一键三连，小编尽全力做到更好
欢迎您分享给更多人哦

今天我们来学习七大排序算法

一：直接插入排序

  /*** 时间复杂度：最好：O(n)：本身就是有序的{1,2,3,4,5}** 最坏 O(n^2):{5,4,3,2,1}** 空间复杂度：O(1);(没有额外的申请空间)** 稳定性：稳定的排序** @param array*/public static void insertSort(int[] array){for (int i = 1; i < array.length; i++) { //第一个元素就不用比较了，直接看第二个元素能不能插进去，i：每次要插入的元素的下标int j = i - 1;int tmp = array[i];for (; j >= 0 ; j--) {if(array[j] > tmp){ //加等号就不稳定了array[j + 1] = array[j];//你往前移动，让tmp插进去}else{break;}}array[j +1] = tmp;//一个是循环里刚好(array[i] < tmp):array[j+1] = tmp;}}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度： O(1) ，它是一种稳定的排序算法

4. 稳定性：稳定

二：希尔排序（缩小增量排序）

    public static void shellSort(int[] array){int gap = array.length;while(gap > 1){gap /= 2;shell(array,gap);}}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;}}

关于希尔排序的时间复杂度：一般认为是并且是不稳定的

三： 选择排序（1）

3.1： 选择排序（1）

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，,第二次从第二个位置开始~直到全部待排序的数据元素排完 。

/*** 时间复杂度：O(n^2）（不管怎么样都是）(n-1)+……+2+1* 空间复杂度：O(1)* 稳定性：不稳定*  堆排序* @param array*/public static void chanceSort(int[] array){//{ 9,3,5,6,2,4}//首先就是第一个数字和后面的所有数字进行比较，找到一个最小的数字放在最前面//譬如第一遍首先最小的是9，然后变成3，最后变成了2的下标
//第二次从第二个元素开始往后找、找最小的元素for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i +1; j < array.length; j++) {if(array[j] < array[minIndex]){minIndex = j;}}swap(array , minIndex,i);}}

【 直接选择排序的特性总结 】

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度： O(N^2)（不管怎么样都是O(n)）

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

4. 稳定性：不稳定

3.2： 选择排序（2）

public static void chanceSort2(int[] array){//我的评价是不如上面那个方法，因为你俩的的时间复杂度完全一样//{ 9,3,5,6,2,4}int left = 0;int right = array.length-1;while(left < right){ //你俩相遇了就不用比了int maxIndex = left;int minIndex = left;//这个i = left +1(从第二个元素和第一个元素进行比较）for (int i = left + 1; i <= right;i++) {//right = array.lengthif(array[i] < array[minIndex]){minIndex = i;}//找到最大的元素放在最后if(array[i] > array[maxIndex]){maxIndex = i;}}swap(array , minIndex,left);//最大值刚好在最小值的位置，所以说最大值已经被交换到了“现在的minIndex的位置”if(maxIndex == left){maxIndex = minIndex;}swap(array,maxIndex,right);left++;right--;}}

四：堆排序(Heapsort)

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

public static void heapSort(int[] array){createBigHeap(array);//创建一个大根堆int end = array.length -1;//为什么要一开始end = array.length-1呢因为，我向下调整的时候不需要调整最后一个元素（最大的一个元素）while(end != 0) {swap(array, 0, end);//交换是肯定要交换最后一个元素啦shiftDown(0, array,end);//这里传的是array.length -1(不需要调整最后那个大的元素）end --;}}public static void createBigHeap(int []array){for (int parent = (array.length-1 -1)/2; parent >= 0; parent--) {shiftDown(parent,array,array.length);//这里减一}}private static void shiftDown(int parent, int []array,int end) {int child = parent *2 +1;while(child < end){ //我创建大根堆的时候传过来的end =array.length//但是我堆排序的时候每次不需要调整最后一个元素了，所以传过来的是array.length-1if(child +1 < end && array[child] < array[child +1]){ //更改child++;}if(array[child] > array[parent]){swap(array,parent,child);parent = child;child = parent *2 +1;}else{break;}}}

五：交换排序

 /*** 2. 时间复杂度：O(N^2),经过改良之后最小为O(n)(完全有序，走一遍就break了）* 3. 空间复杂度：O(1)* 4. 稳定性：稳定* @param array*/public static void bubbleSort(int[] array){for (int i = 0; i < array.length; i++) {boolean flag = false;for (int j = 0; j < array.length -1 -i; j++) {if(array[j] > array[j+1]){swap(array,j,j+1);flag = true;}}if(flag == false){break;}}}

六：快速排序

public static void quickSort(int[] array){quick(array,0,array.length -1);}public static void quick(int[] array,int start,int end) {if(start >= end){return;}int pivot = quickSortSmall(array,start,end);quick(array,start,pivot- 1);//这里一定要注意开始的边界一定要是start,不能是0
//你要想想如果，现在正在递归我右边的左边（这个起始其实应该是pivot+1）quick(array,pivot +1,end);}public static int  quickSortSmall(int[] array, int left, int right){int location = left;//保留我原来的最左边的下标int key = array[left];while(left < right){while(left < right && array[right] >= key){ //大循环里面的小循环一定要注意边界right--;}while(left < right && array[left] <= key){//都要加等号，不然可能走不动呀left++;}swap(array,left,right);}swap(array , location,left);让相遇点下标的值和我的起始值进行交换
//每次相遇的时候的值都小于等于我的起始值，
//情况一：right动到left(由于right先动的，left还处于上一次交换完的<key
//情况二：left动到了right，想都不用想，right先动到了小于key的值
//情况三：一开始left就没动过，right一下就到了left（相当于这个树没有左子树）return left;}

Test：测试七大排序算法

（冒泡除外）

import java.util.Arrays;
import java.util.Random;public class Test {public static void orderArray(int[] array){for (int i = 0; i < array.length; i++) {array[i] = i;}}public static void notOrderArray(int[] array){for (int i = 0; i < array.length; i++) {array[i] = array.length - i;}}public static void randomArray(int[] array){Random random = new Random();for (int i = 0; i < array.length; i++) {array[i] = random.nextInt(100000);}}public static void testInsertSort(int[] array){//这样不对 ：int []tmpArray = array;//要copy，不然你给我排序了，后面的就是有序了呀int[] tmpArray = Arrays.copyOf(array,array.length);//开始和结束的时间long startTime = System.currentTimeMillis();Sort.insertSort(tmpArray);long endTime = System.currentTimeMillis();//这里一定要加括号呀，不然就相当于你一个字符串减去一个数字，肯定报错System.out.println("插序消耗时间:" + (endTime - startTime));}public static void main2(String[] args) {int[] array = new int[10000];//orderArray(array);notOrderArray(array);//randomArray(array);testInsertSort(array);testShellSort(array);testQuickSort(array);testHeapSort(array);}public static void main(String[] args) {//int[] array = new int[100000];int []array = {4,5,3,8,2};Sort.bubbleSort(array);//Sort.shellSort(array);//Sort.chanceSort2(array);//Sort.heapSort(array);//Sort.quickSort(array);System.out.println(Arrays.toString(array));}
}

上述就是排序算法漫游：从冒泡到堆排的底层逻辑与性能厮杀

的全部内容了，能看到这里相信您一定对小编的文章有了一定的认可。

有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正~~

您的支持就是我最大的动力​​​！！！！