基础排序算法概述

1.选择排序

        每次从未排序的部分选择最小（或最大）的元素放到已排序部分的末尾，时间复杂度，空间复杂度，且不稳定；

public void selectionSort(int[] nums){
    if(nums==null || nums.length < 2) return;
    for(int min, i = 0; i < nums.length - 1; i++){
        min = i;
        for(int j = i + 1; j < nums.length; j++){
            if(nums[j] < nums[min]){
                min = j;
            }
        }
        swap(nums,i,min);
    }
}

2.冒泡排序

        每次将相邻的两个元素进行比较和交换，使得较大（或较小）的元素逐渐移动到数组的末尾，时间复杂度为，空间复杂度为，且稳定；

public void bubbleSort(int[] nums){
    if(nums==null || nums.length < 2) return;
    for (int i = nums.length - 1; i > 0; i--){
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j+1]){
                swap(nums,j,j+1);
            }
        }
    }
}

3.插入排序

        每次从未排序数据中选一个数据，从后到前扫描已排序序列，找到数据位置插入，时间复杂度为，空间复杂度为，且稳定；

public void insertionSort(int[] nums){
    if(nums==null || nums.length < 2) return;
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0 && nums[j] < nums[j-1]; j--) {
            swap(nums,j,j-1);
        }
    }
}

4.归并排序

        采用分治法的思想，将数组分成两部分，分别对这两部分进行排序，然后将两个有序的子数组合并成一个有序的数组，时间复杂度，空间复杂度，且稳定；

public int[] help = new int[MAX];
public void mergeSort(int[] nums){
    int length = nums.length;
    for (int left, mid, right, step = 1; step < length; step <<= 1){
        left = 0;
        while (left < length){
            mid = left + step - 1;
            if (mid >= length -1){
                break;
            }
            right = Math.min(left+(step << 1) -1, length -1);
            merge(nums,left,mid,right);
            left = right + 1;
        }
    }
}
public void merge(int[] nums, int left, int mid, int right){
    int i = left, j = left;
    int k = mid+1;
    while (j <= mid && k <= right){
        help[i++] = nums[j] <= nums[k] ? nums[j++] : nums[k++];
    }
    while (j <= mid){
        help[i++] = nums[j++];
    }
    while (k <=right){
        help[i++] = nums[k++];
    }
    for (i = left; i <= right; i++){
        nums[i] = help[i];
    }
}

5.快速排序

        采用分治法的思想，随机选择一个基准值，通过基准值将数组分成两部分，然后对两部分分别排序，时间复杂度，空间复杂度，且不稳定；

public int first,last;
public void quickSort(int[] nums, int left, int right){
    if (left > right){
        return;
    }
    int x = nums[left + (int)(Math.random()*(right - left + 1))];
    partition(nums,left,right,x);
    int a = first;
    int b = last;
    quickSort(nums,left,a-1);
    quickSort(nums,b+1,right);
}
public void partition(int[] nums, int left, int right, int x){
    first = left;
    last = right;
    int i = left;
    while (i < last){
        if (nums[i] == x){
            i++;
        } else if (nums[i] < x) {
            swap(nums,first++,i++);
        }else{
            swap(nums,i,last--);
        }
    }
}

6.堆排序

        基于二叉堆结构，利用大根堆（小根堆）的性质实现排序，时间复杂度，空间复杂度，且不稳定；

public void heapSort(int[] nums){
    int length = nums.length;
    for (int i = length - 1; i >= 0; i--){
        heapify(nums,i,length);
    }
    int size = length;
    while (size > 1){
        swap(nums,0,--size);
        heapify(nums,0,size);
    }
}
public void heapify(int[] nums, int index, int size){
    int left = index * 2 + 1;
    while (left < size){
        int best = left + 1 < size && nums[left+1] > nums[left] ? left+1 : left;
        best = nums[best] > nums[index] ? best : index;
        if (best == index){
            break;
        }
        swap(nums,best,index);
        index = best;
        left = index * 2 + 1;
    }
}

7.基数排序

        与上面这些排序算法不同，基数排序是一种不基于比较的排序算法，将每个数据从最低位开始逐位进行排序，时间复杂度，空间复杂度，且稳定；

private static int BASE = 1000;
private static int MAX = 50001;
private static int[] cnts = new int[BASE];
public int[] help = new int[MAX];
public int[] sortArray(int[] nums) {
    //查找最小值
    int length = nums.length;
    int min = nums[0];
    for (int i = 0; i < length; i++) {
        min = Math.min(min, nums[i]);
    }
    //获取最大值
    int max = 0;
    for (int i = 0; i < length; i++) {
        nums[i] -= min;
        max = Math.max(max, nums[i]);
    }
    //获取最大值的位数
    int maxLength = 0;
    while (max != 0) {
        maxLength++;
        max = max / BASE;
    }
    radixSort(nums,length, maxLength);
    //还原数组
    for (int i = 0; i < length; i++) {
        nums[i] += min;
    }
    return nums;
}

private void radixSort(int[] nums, int length, int maxLength) {
    for (int offset = 1; maxLength > 0; offset *= BASE, maxLength--){
        Arrays.fill(cnts, 0);
        for (int i = 0; i < length; i++) {
            cnts[(nums[i]/offset)%BASE]++;
        }
        for (int i = 1; i < BASE; i++) {
            cnts[i] += cnts[i-1];
        }
        for (int i = length-1; i >= 0 ; i--) {
            help[--cnts[(nums[i]/offset)%BASE]] = nums[i];
        }
        for (int i = 0; i < length; i++) {
            nums[i] = help[i];
        }
    }
}

8.总结

• 数据量很小的情况下直接用插入排序比较快且易于实现；
• 性能优异、实现简单、不在乎稳定性且利于改进，选择随即快排；
• 性能优异、不在乎额外空间占用、在乎稳定性，选择归并排序；
• 性能优异、需要额外空间占用低、不在乎稳定性，选择堆排序；