排序算法

冒泡排序

从前往后两两比较，排最大。

public static int[] bubbleSort(int[] nums) {
        for(int i = nums.length; i > 1; --i) {
            for (int j = 0; j < i-1; ++j) {
                int a = nums[j];
                int b = nums[j+1];
                if (a > b) {
                    nums[j+1] = a;
                    nums[j] = b;
                }
            }
        }
        
        return nums;
    }

选择排序

从前往后两两比较，记下最小的位置，排最小。

public static int[] selectSort(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            int pos = i;
            for (int j = i+1; j < nums.length; ++j) {
                if (nums[pos] > nums[j]) {
                    pos = j;
                }
            }
            int tmp = nums[pos];
            nums[pos] = nums[i];
            nums[i] = tmp;
        }
        
        return nums;
    }

插入排序

从第二个位置，往前找自己的位置。

public static int[] insertSort(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            
            /* 这里是从前往后比较，但是因为i之前的数字全是都排列过的，所以从后往前比较速度更快
            int tmp1 = nums[i];
            for (int j = 0; j < i; ++j) {
                if (tmp1 < nums[j]) {
                    int tmp2 = nums[j];
                    nums[j] = tmp1;
                    tmp1 =tmp2;
                }
            }
            */
            int j = i - 1;
            int insertNum = nums[i];
            while (j >=0 && nums[j] > insertNum) {
                nums[j+1] = nums[j];
                --j;
            }
            
            nums[j+1] = insertNum;
        }
        
        return nums;
    }

前三张算法的时间复杂度都是log(n^2).

快速排序

选择一个基准点，将所有小于基准的排到基准左边，所有大于基准的排到基准右边,递归。
时间复杂度：O(nlogn)
空间复杂度：O(logn)
快速排序的效率高于归并排序，但在最坏情况下的时间复杂度为O(n^2)。

public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int pivot = nums[left+(right-left)];
        
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            
            while (left <= right && nums[right] > pivot) {
                  right--;
            }
            
            if (left<=right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
        quickSort(nums, start, right);
        quickSort(nums, left, end);
    }

归并排序

将数组分成n份，两两结合排序
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，因为需要额外使用一个与原序列同样大小的辅助数组。

public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];
        mergeSortImpl(array, 0 , array.length - 1, temp);
    }

    public static void mergeSortImpl(int[] array, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSortImpl(array, start, mid, temp);
        mergeSortImpl(array, mid + 1, end, temp);
        merge(array, start, mid, end, temp);
    }

    public static void merge(int[] array, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid + 1;
        int index = start;
        while(left <= mid && right <= end) {
            if (array[left] < array[right]) {
                temp[index++] = array[left++];
            } else {
                temp[index++] = array[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = array[left++];
        }
        while (right <= end) {
            temp[index++] = array[right++];
        }
        for (index = start; index <= end; index++) {
            array[index] = temp[index];
        }
    }