排序

https://leetcode-cn.com/problems/sort-an-array/

选择排序

平均：
最坏：
因为要将最小值调换到前面，不稳定

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    for(int i = 0; i < numsSize; i++){
        int min = i;
        for(int j = i + 1; j < numsSize; j++){
            if(nums[j] < nums[min]){
                min = j;
            }
        }
        if(min != i){
            int temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
    }
    return nums;
}

public static int[] selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int currentMin = i; //当前最小值下标
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[currentMin])
                currentMin = j;
        }
        if (currentMin != i) {
            int temp = nums[i];
            nums[i] = nums[currentMin];
            nums[currentMin] = temp;
        }
    }
    return nums;
}

冒泡排序

平均：
最坏：倒序，
稳定

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    for(int i = 1; i < numsSize; i++){
        for(int j = 0; j < numsSize - i; j++){
            if(nums[j] > nums[j + 1]){
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    return nums;
}

public static int[] bubbleSort(int[] nums) {
    int temp;
    boolean flag;
    for (int p = nums.length - 1; p > 0; p--) {
        flag = false;
        for (int i = 0; i < p; i++) { //一趟冒泡
            if (nums[i] > nums[i + 1]) {
                temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
                flag = true;
            }
        }
        if (!flag) //全程无交换
            break;
    }
    return nums;
}

插入排序

平均：
最坏：倒序，
最好：顺序，
稳定

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    for(int i = 1; i < numsSize; i++){
        int temp = nums[i];
        int j = i;
        while(j > 0 && nums[j - 1] > temp){
            nums[j] = nums[j - 1];
            j--;
        }
        nums[j] = temp;
    }
    return nums;
}

public static int[] insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int temp = nums[i];
        while (i > 0 && temp < nums[i - 1]) {
            nums[i] = nums[i - 1]; //将下标i-1空出来
            i--;
        }
        nums[i] = temp;
    }
    return nums;
}

任意N个不同元素组成的序列平均具有 N(N-1)/4 个逆序对
任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为

希尔排序

平均：
最坏：

public static int[] shellSort(int[] nums) {
    int c = 0;
    int[] Sedgewick = {929, 505, 209, 109, 41, 19, 5, 1, 0};
    //增量不能超过数组长度
    while (Sedgewick[c] >= nums.length)
        c++;
    for (int d = Sedgewick[c]; d > 0; d = Sedgewick[++c]) {
        for (int i = d; i < nums.length; i += d) {
            int temp = nums[i];
            while (i > 0 && temp < nums[i - d]) {
                nums[i] = nums[i - d];
                i = i - d;
            }
            nums[i] = temp;
        }
    }
    return nums;
}

归并排序

无论如何
额外空间：
稳定

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int* temp = (int *)malloc(sizeof(int) * numsSize);
    sort(nums, 0, numsSize - 1, temp);
    return nums;
}

void sort(int* nums, int left, int right, int* temp){
    if(left >= right)
        return;
    int middle = (left + right) / 2;
    sort(nums, left, middle, temp);
    sort(nums, middle + 1, right, temp);
    merge(nums, left, middle + 1, right, temp);
}

void merge(int* nums, int left, int right, int rightEnd, int* temp){
    int leftEnd = right - 1;
    int p = left;
    int count = rightEnd - left + 1;
    while(left <= leftEnd && right <= rightEnd){
        if(nums[left] <= nums[right]){
            temp[p] = nums[left];
            left++; 
        }
        else{
            temp[p] = nums[right];
            right++; 
        }
        p++;
    }
    while(left <= leftEnd){
        temp[p] = nums[left];
        left++;
        p++;
    }
    while(right <= rightEnd){
        temp[p] = nums[right];
        right++;
        p++;
    }
    for(int i = 0; i < count; i++){
        nums[rightEnd] = temp[rightEnd];
        rightEnd--;
    }
}

import java.util.Arrays;

class Solution {

    private static int[] temp;

    public static int[] mergeSort(int[] nums) {
        temp = new int[nums.length]; //在最外层申请额外空间
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void sort(int[] nums, int low, int high) {
        if (high <= low)
            return;
        int mid = (high + low) / 2;
        sort(nums, low, mid); //递归对左半边排序
        sort(nums, mid + 1, high);
        if (nums[mid] >= nums[mid + 1]) //若已为顺序则不必进入排序
            merge(nums, low, mid + 1, high);
    }

    //left左边起始位置，right右边起始位置，rightEnd终点位置
    public static void merge(int[] nums, int left, int right, int rightEnd) {
        int k = left;
        int leftEnd = right - 1;
        int count = rightEnd - left + 1;
        while (left <= leftEnd && right <= rightEnd) {
            //这里的等号使得归并排序是稳定的
            if (nums[left] <= nums[right]) {
                temp[k] = nums[left];
                left++;
            } else {
                temp[k] = nums[right];
                right++;
            }
            k++;
        }
        while (left <= leftEnd) {
            temp[k] = nums[left];
            left++;
            k++;
        }
        while (right <= rightEnd) {
            temp[k] = nums[right];
            right++;
            k++;
        }

        for (int i = 0; i < count; i++, rightEnd--) {
            nums[rightEnd] = temp[rightEnd];
        }

    }

    public static void main(String[] args) {
        int[] test = new int[]{4, 3, 2, 1};
        System.out.println(Arrays.toString(mergeSort(test)));
    }
}

快速排序

平均：
最坏：
额外空间：

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public int getMedium(int[] nums, int left, int right){
        int center = (left + right) / 2;
        int temp;
        if(nums[left] > nums[right]){
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        if(nums[left] > nums[center]){
            temp = nums[left];
            nums[left] = nums[center];
            nums[center] = temp;
        }
        if(nums[center] > nums[right]){
            temp = nums[center];
            nums[center] = nums[right];
            nums[right] = temp;
        }
        temp = nums[center];
        nums[center] = nums[right - 1];
        nums[right - 1] = temp;

        return nums[right - 1];
    }

    public void sort(int[] nums, int left, int right){
        if(right - left > 0){
            int pivot = getMedium(nums, left, right);
            //如果不设置cutoff使用插入排序一定要判断条件
            if(right - left > 2){
                int temp;
                int i = left + 1;
                int j = right - 2;
                while(true){
                    while(nums[i] < pivot)
                        i++;
                    while(nums[j] > pivot)
                        j--;
                    if(i < j){
                        temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                    }
                    else break;
                }
                temp = nums[i];
                nums[i] = nums[right - 1];
                nums[right - 1] = temp;
                sort(nums, left, i - 1);
                sort(nums, i + 1, right);                
            }
        }
    }
}

堆排序

• 建堆，删除，导回，时间复杂度为，需要额外额外空间
• 建最小堆，将堆顶与最后一个元素交换，此时最后一个元素已固定，不需要额外空间，时间复杂度较上面小