排序算法

5.1 常用的排序算法

快速排序（Quicksort）

此处采用左闭右闭的二分写法。

private static void quickSort(int[] nums, int start, int end){
        if(start+1 >= end) return;

        int left=start, right=end-1, key=nums[left];
        while (left < right){
            while (left<right && nums[right]>= key){
                right--;
            }
            nums[left] = nums[right];
            while (left<right && nums[left]<=key){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        quickSort(nums, start, left);
        quickSort(nums, left+1, end);
    }

归并排序（Merge Sort）

private static void mergeSort(int[] nums, int[] tmp, int left, int right){
        if(left>=right) return;
        int mid = (left+right)/2;
        // 二路归并，所以是2个mergeSort()
        mergeSort(nums, tmp, left, mid);
        mergeSort(nums, tmp, mid+1, right);
        merge(nums, tmp, left, mid, right);
    }

    private static void merge(int[] nums, int[] tmp, int start, int mid, int end){
        int left_start=start, right_start=mid+1, i=0;
        while (left_start<=mid && right_start<= end){
            // tmp中为升序，挑取nums[]左右两分支中的，小的那个（从左往右遍历）
            tmp[i++] = nums[left_start]<nums[right_start]? nums[left_start++]: nums[right_start++];
        }
        // 若左边分支还有剩余，则全部拷贝进tmp[]
        while (left_start<=mid){
            tmp[i++] = nums[left_start++];
        }
        // 若右边分支还有剩余，全部拷贝进tmp[]
        while (right_start<=end){
            tmp[i++] = nums[right_start++];
        }
        // tmp[:i] => nums[start: start+i] 左闭右开
        System.arraycopy(tmp, 0, nums, start, i);
    }

插入排序（Insertion Sort）

private static void insertionSort(int[] nums){
        int tmp;
        for(int i=0; i<nums.length; i++){
            for(int j=i; j>0 && nums[j]<nums[j-1]; j--){
                tmp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = tmp;
            }
        }
    }

冒泡排序（Bubble Sort）

private static void bubbleSort(int[] nums){
        boolean swapped;
        int tmp;
        for(int i=1; i<nums.length; i++){
            swapped = false;
            for(int j=1; j<(nums.length-i)+1; j++){
                if(nums[j] < nums[j-1]){
                    tmp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = tmp;
                    swapped = true;
                }
            }
            if(!swapped) break;
        }
    }

选择排序（Selection Sort）

private static void selectionSort(int[] nums){
        int mid, tmp;
        for(int i=0; i<nums.length-1; i++){
            mid = i;
            for(int j=i+1; j<nums.length; j++){
                if(nums[j] < nums[mid]){
                    mid = j;
                }
            }
            tmp = nums[mid];
            nums[mid] = nums[i];
            nums[i] = tmp;
        }
    }

5.2 快速选择

215. Kth Largest Element in an Array

     题目描述

     在一个未排序的数组中，找到第K大的数字。

     输入输出样例

     输入一个数组和一个目标值K，输出第K大的数字，默认有解。

     Input: [3,2,1,5,6,4] and k = 2
     Output: 5
     

     题解

     快速选择一般用于求解Kth Element问题，可以在O(n)时间复杂度和O(1)空间复杂度完成求解。

     快速选择的实现和快速排序相似，只不过需要找到第K大的枢（pivot）即可，不需要对其左右再进行排序，与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为O(n^2)。此处省略打乱步骤。

     private static int quickSelect(int[] nums, int k){
             int left=0, right=nums.length-1, mid, target=nums.length-k;
             while (left < right){
                 mid = helpFunc(nums, left, right);
                 if(mid < target){
                     left = mid + 1;
                 }else if(mid == target){
                     return nums[mid];
                 }else{
                     right = mid + 1;
                 }
             }
             return nums[left];
         }
         // 辅助函数 - 快速选择
         private static int helpFunc(int[] nums, int left, int right){
             int i=left+1, j=right, tmp;
             while (true){
                 while (i<right && nums[i]<=nums[left]){
                     i++;
                 }
                 while (left<j && nums[j]>=nums[left]){
                     j--;
                 }
                 if(i>=j) break;
                 tmp = nums[i];
                 nums[i] = nums[j];
                 nums[j] = tmp;
             }
             tmp = nums[left];
             nums[left] = nums[j];
             nums[j] = tmp;
             return j;
         }
     

5.3 桶排序

347. Top K Frequent Elements(Medium)

     题目描述

     给定一个数组，求前K个最频繁的数字。

     输入输出样例

     输入是一个数组和一个目标值K，输出是一个长度为K的数组。

     Input: nums = [1,1,1,1,2,2,3,4], k = 2
     Output: [1,2]
     

     题解

     ? 顾名思义，桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数（或其他属性），然后对桶进行排序。先通过桶排序得到4个桶[1,2,3,4]，他们的值分别为[4,2,1,1]，表示每个数字出现的次数。

     ? 紧接着，按桶内的属性对4个桶进行排序（升序），这里可以使用任意排序算法，后K个桶就是需要的。

排序算法

原文：https://www.cnblogs.com/pangqianjin/p/14257356.html