排序算法

排序

快速排序

快速排序是排序算法中平均时间复杂度为O(nlogn)的一种算法。

思路：

从数组中选择一个数字，使得该数字左面都是小于该数字的数，右面都是大于该数字的数。再分别对该数字的左半部分和右半部分分别执行这种操作，直到数组区间中只剩一个数字，即可得到有序数列。

当数组本身有序时，时间复杂度会达到O(n^2)，因为选择的主元没有把当前区间切分为两个长度差别不大的区间。

实现：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }
    private void quickSort(int[] arr, int l, int r){
        if(l>=r) return;
        int i = partition(arr, l, r);
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    private int partition(int[] arr, int l, int r){
        int temp = arr[l];
        while(l < r){
            while(l < r && arr[r] >= temp){
                r--;
            }
            arr[l] = arr[r];
            while(l < r && arr[l] <= temp){
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = temp;
        return l;
    }
}

相关题目： 排序

归并排序

归并排序是一种稳定的时间复杂度为O(nlogn)的排序算法。

思路：

一个数组的左半部分是有序的，右半部分也是有序的，通过从两端头开始比较可得到一个完整的有序数组。

实现：

public void mergeSort(int[] arr, int l, int r, int[] temp){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(arr, l, mid, temp);
        mergeSort(arr, mid + 1, r, temp);
        int i = l, j = mid + 1;
        int idx = l;
        while(i <= mid && j <= r){
            if(arr[i] <= arr[j]){
                temp[idx++] = arr[i++];
            }else{
                temp[idx++] = arr[j++];
            }
        }
        while(i <= mid){
            temp[idx++] = arr[i++];
        }
        while(j <= r){
            temp[idx++] = arr[j++];
        }
        for(i = l; i < idx; i++){
            arr[i] = temp[i];
        }
    }

注意：分界点是mid和mid+1，不要多次创建temp数组，创建对象的开销特别大。