---

排序

---

选择排序

• 在待排序序列中，找到最小值（大）的下标，和排好序的末尾交换，放到待排序列的开头，直到全部待排序元素排完
  

1.直接选择排序

方法一

​

    /*** 选择排序** @param array*/public static void selectSort(int[] array) {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;//只要比minIndex小，放进去}}//循环走完后，minIndex存的就是当前未排序的最小值//将当前i的值和找到的最小值进行交换swap(array,i,minIndex);}}public static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

1.遍历数组长度，i从0开始

2.每次循环，都由minIndex = i 来记录最小值的下标

3.j 从i+1开始遍历，只要比记录的最小值小，就让minIndex记录。找到未排序中的最小值，进行交换

4.如果遍历完后，未排序中没有比minIndex存的值小，i的值就是最小值，i++;

• 效率低, 如果较为有序的序列，在交换时会破坏有序性
• 时间复杂度：O ( N² )
• 空间复杂的：O ( 1 )
• 稳定性：不稳定

方法二

• 上面的方法，只是先选出最小的值，然后和i的位置交换，

• 进行优化：在遍历时选出最大值和最小值，和收尾进行交换

   /*** 选择排序---选最大值和最小值** @param array*/public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;//选出最大值和最小值for (int i = left + 1; i <= right; i++) {if (array[i] > array[maxIndex]) {maxIndex = i;}if (array[i] < array[minIndex]) {minIndex = i;}}//用最大值和最小值交换首位swap(array, left, minIndex);//把left和最小值交换//如果left恰好就是最大值，就有可能把最大值换到minIndex的位置if(left == maxIndex){maxIndex = minIndex;//最大值位置不是left了，而是换到了minIndex}swap(array, right, maxIndex);left++;right--;}}

1.在遍历的过程中，选出最大值的下标和最小值的下标

2.将left和最小值进行交换

3.如果left恰好为最大值，left和最小值交换完成后，最大值就在原来最小值的位置上，

4.maxIndex = minIndex,修正最大值的位置

4.将right和最大值进行交换

直接插入排序和直接排序的区别

• 和插入排序不同的是，插入排序会持续对已排序的数进行比较，把合适的数放在合适的位置
• 直接选择排序就是不断找到最小的值，依次放在排好序的末尾，不干预排好的序列

2.堆排序

• 时间复杂度: O( N * log N)
• 空间复杂的：O (1)

• 升序：建大堆

• 降序：建小堆

将一组数据从小到大排序 ——> 建立大根堆

为什么不用小根堆：小根堆只能保证，根比左右小，不能保证左右孩子的大小顺序，并且要求对数组本身进行排序

• 大根堆，保证堆顶元素是最大值，最大值跟最后一个元素交换，将最大的放在最后，usedSize–；
• 向下调整：调整0下标的树，维护大根堆，最大值继续交换到最后一个有效元素的位置
• 从后往前，从大到小依次排列，保证在原来数组本身进行排序

    /*** 堆排序* 时间复杂度: N*logN* 空间复杂的：o(1)** @param array*/public static void heapSort(int[] array) {createBigHeap(array);//创建大根堆int end = array.length-1;while (end>0){swap(array,0,end);//堆顶元素和末尾互换shiftDown(array,0,end);//维护大根堆end--;}}/*** 创建大根堆** @param array*/public static void createBigHeap(int[] array) {//最后一个结点的下标 = array.length - 1//它的父亲结点的下标就为array.length - 1 - 1) / 2for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {shiftDown(array, parent, array.length);}}/*** 向下调整** @param array* @param parent* @param len*///向下调整，每棵树从父结点向下走public static void shiftDown(int[] array, int parent, int len) {int child = parent * 2 + 1;while (child < len) {//child < len:最起码要有一个左孩子if (child + 1 < len && array[child] < array[child + 1]) {child++;}//child + 1<len:保证一定有右孩子的情况下，和右孩子比较//拿到子节点的最大值if (array[child] > array[parent]) {swap(array, child, parent);parent = child;//交换完成后，让parent结点等于等于当前child结点child = 2 * parent + 1;//重新求子节点的位置，再次进入循环交换} else {break;//比父结点小，结束循环}}}

• 时间复杂度: O( N * log ₂N)
• 空间复杂的：O (1)
• 稳定性：不稳定

点击移步博客主页，欢迎光临~