不具备稳定性的排序：抉择排序、疾速排序、堆排序

具备稳定性的排序：冒泡排序、插入排序、归并排序（nlogn）

抉择排序

每次遍历找到数组中最小的元素的索引，顺次替换。

public int[] sortArray (int[] nums) {       for(int i=0; i<nums.length; i++) {        int minIndex = i;        for(int j=i+1; j<nums.length; j++) {            minIndex = nums[j] < nums[minIndex] ? j : minIndex;         }        swap(nums, i, minIndex);    }    return nums;}

疾速排序

  • 疾速排序是由上到下的，先分区，而后再解决子问题。

基本思路：

  1. 先从数组中找一个基准数
  2. 让其余比它大的元素挪动到数组一边，比他小的元素挪动到数组另一边。从而把数组拆解成两局部。
  3. 再对左右区间反复第二部，直到各区间只有一个数。

low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，而后两个元素替换地位，最初再将基准数归位。

  • 填坑法
public void quickSort (int[] nums, int low, int high) {    if(low < high) {        int index = partition(nums, low, high);        quickSort(nums, low, index-1);        quickSort(nums, index+1, high);    }}public int partition(int[] nums, int low, int high) {    int pivot = nums[low];    while(low < high) {        while(low<high && nums[high] >= pivot) {            high--;        }        nums[low] = nums[high];        while(low<high && nums[low] <= pivot) {            low++;        }        nums[high] = nums[low];    }    nums[low] = pivot;    return low;}
  • 交换法

其实这种办法，算是对下面办法的挖坑填坑步骤进行合并，low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，而后两个元素替换地位，最初再将基准数归位。

public void quickSort (int[] nums, int low, int high) {    if(low < high) {        int index = partition(nums, low, high);        quickSort(nums, low, index-1);        quickSort(nums, index+1, high);    }}public int partition(int[] nums, int low, int high) {    int pivot = nums[low];    int start = low;    //记录low指针    while(low < high) {        while(low < high && nums[high] >= pivot)  high--;        while(low < high && nums[low] <= pivot)    low++;        if(low >= high) {            break;        }                      swap(nums, low, high);     }    //基准值归位    swap(nums, start, low);    return low;}    public void swap(int[] nums, int i, int j) {        if(i == j) return;        nums[i] = nums[i] ^ nums[j];        nums[j] = nums[i] ^ nums[j];        nums[i] = nums[i] ^ nums[j];    }

冒泡排序

两两比拟相邻记录的关键字，如果是反序则替换，直到没有反序为止。

public int[] sortArray(int[] nums) {            for(int i=0; i<nums.length; i++) {        for(int j=0; j<nums.length-i-1; j++) {            if(nums[j] > nums[j+1]) {                swap(nums, j, j+1);            }        }    }    return nums;}private void swap(int[] arr, int i, int j) {    int temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}

冒泡排序能够用 标识flag 改良，如果替换则标识位发生变化，如果标识为没有变动，阐明曾经排序好了！

插入排序

一直地与后面的数字比拟，如果后面的数字比它大，它就和后面的数字替换地位。

public int[] sortArray(int[] nums) {    for(int i=1; i<nums.length; i++) {        int j = i;  //记录以后数字下标        //以后数字比前一个数字小，则替换        while(j >= 1 && nums[j] < nums[j-1]) {            swap(nums, j, j-1);            j--;  //持续向前一个元素比拟        }    }    return nums;}public void swap(int[] nums, int i, int j) {    int temp = nums[i];    nums[i] = nums[j];    nums[j] = temp;}

归并排序

  • 归并排序采纳的是 分治法 思维。
  • 整体就是简略的递归，右边排好序，左边排好序，再让其整体有序。怎么整体有序呢？筹备一个辅助空间，看看两边排好序的右边，比拟谁小就谁先进入这个辅助空间（外排序办法）
  • 归并排序中的比拟次数是所有排序中起码的，它一开始是一直地划分，比拟只产生在合并各个有序的子数组时。

public int[] sortArray (int[] nums) {       int[] temp = new int[nums.length];       mergeSort(nums, 0, nums.length-1, temp);    return nums;     }public void mergeSort(int[] nums, int low, int high, int[] temp) {    int mid = (low + high) / 2;    if(low < high) {        //对左右进行拆分        mergeSort(nums, low, mid, temp);        mergeSort(nums, mid+1, high, temp);        //合并        merg(nums, low, high, mid, temp);    }}public void merg(int[] nums, int low, int high, int mid, int[] temp) {    int index = 0;    int i = low;        //右边序列起始索引    int j = mid + 1;    //左边序列起始索引            while(i <= mid && j <= high) {        if(nums[i] <= nums[j]) {            //这里最好用 <=            temp[index++] = nums[i++];        } else {            temp[index++] = nums[j++];        }    }    //若右边序列还有残余    while(i <= mid) {        temp[index++] = nums[i++];    }    //若左边序列还有残余    while(j <= high) {        temp[index++] = nums[j++];    }    //把temp数组的赋值给原数组nums    for(int t=0; t<index; t++) {        nums[low + t] = temp[t];    }}

工夫复杂度为：O(NlogN)

额定空间复杂度为：O(N)

堆排序

  • 二叉堆，必须是齐全二叉树，而且二叉堆中的每一个节点，都必须大于等于（或小于等于）其子树中每个节点的值。

  • 因为堆是齐全二叉树，所以咱们齐全能够用数组存储。将根节点的下标视为 0，则齐全二叉树有如下性质：

    • 它的左子节点下标：2i + 1
    • 它的右子节点下标：2i + 2
    • 对于有 n 个元素的齐全二叉树（n >2），它的最初一个非叶子结点的下标：n/2 - 1

构建大顶堆：将整个数列的初始状态视作一棵齐全二叉树，自底向上调整树的构造，使其满足大顶堆的要求。

变量 heapSize 用来记录还剩下多少个数字没有排序实现，每当替换了一个堆顶的数字，heapSize 就会减 1。在 maxHeapify 办法中，应用 heapSize 来限度剩下的选手，不要和曾经躺在数组最初，当过冠军的人比拟，省得被暴揍。

  1. 构建初始大顶堆，从最初一个非叶子节点开始堆化。
  2. 进入循环，将最大值放到数组的最初，并且堆化调整地位。循环最大索引次，排序结束。
public int[] sortArray(int[] nums) {    //构建初始大顶堆    buildMaxHeap(nums);    for(int i=nums.length - 1; i >= 0; i--) {        swap(nums, 0, i);   //将最大值放到数组的最初        maxHeapify(nums, 0, i); //调整残余数组，使其满足大顶堆    }    return nums;}public void buildMaxHeap(int[] nums) {    // 从最初一个非叶子结点开始调整大顶堆，最初一个非叶子结点的下标就是 arr.length / 2-1    for(int i = nums.length / 2 - 1; i>=0; i--) {        maxHeapify(nums, i, nums.length);    }}//调整大顶堆（第三个参数示意残余未排序的数字的数量，也就是残余堆的大小）public void maxHeapify(int[] nums, int i, int heapSize) {    int l = 2 * i + 1;      // 左子结点下标    int r = l + 1;          // 右子结点下标    int largest = i;        //记录根结点和两个儿子之间的最大值    if(l < heapSize && nums[l] > nums[largest])  largest = l;    if(r < heapSize && nums[r] > nums[largest])  largest = r;    //如果有子结点大于根结点，则替换，并用 largest 去再次调整大顶堆。    if(largest != i) {        swap(nums, i, largest);        maxHeapify(nums, largest, heapSize);    }}public void swap(int[] nums, int i, int j) {    int temp = nums[i];    nums[i] = nums[j];    nums[j] = temp;}