力扣刷题——排序题目-白红宇

力扣刷题——排序题目

阅读量：202 次

发布时间：2019-02-28

本文共 5877 字，大约阅读时间需要 19 分钟。

0.JAVA的排序算法实现

java.util.Arrays.sort();
对于原始（即：基本）数据：采用三向切分的快排；
对于引用数据：采用归并。

1.选择排序

从数组中选择最小的元素，将他与第一个元素交换，再从剩下的元素中选择第二小的元素，将他与第二个元素交换，依此类推。

复杂度：

要经过： n²/2 次比较 n次交换

时间复杂度: O(N²)

空间复杂度：O(1)

稳定性不好

class Solution1 {        public int[] sortArray(int[] nums) {            for (int i = 0; i < nums.length; i++) {                int min = Integer.MAX_VALUE;             int index = i;             for (int j = i; j < nums.length; j++) {                    1.记录下标                 index = nums[j]

2.冒泡排序（如何优化？）

1.从左到右不断交换相邻的逆序元素，在一轮循环后，可以让未排序的最大元素上浮到最顶端

2.一轮循环后如果没有发生交换，说明数组有序，可以直接退出；

复杂度：

时间复杂度: O(N²)

空间复杂度：O(1)

稳定

class Solution2 {       public int[] sortArray(int[] nums) {           1.外层for前序遍历        for (int i = 0; i < nums.length; i++) {               2.内层for后序遍历            for (int j = nums.length-1; j >i ; j--) {                   if (nums[i]>nums[j])                    swap(nums,i,j);            }        }        return nums;    }    public void swap(int[] nums,int i,int j){           int temp = nums[i];        nums[i]  = nums[j];        nums[j]  = temp;    }}

3.插入排序

每次把当前元素插入到左侧已经排序的数组中，使得插入后的左侧数组依然有序。
eg.对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：

(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，

插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

复杂度：

平均情况下插入排序需要 N²/4次比较， N²/4次交换

最坏情况下（数组倒序时）： N²/2次比较， N²/2次交换，

最好情况下（数组正序）：N-1 次比较， 0次交换

class Solution4 {       public int[] sortArray(int[] nums) {           for (int i = 1; i < nums.length; i++) {               for (int j = i; j > 0 && nums[j]

4.希尔排序（优化的插入排序）：不稳定

1.对于大规模数组，插入排序很慢，因为它每次只能把逆序的数量减少1

希尔排序优化了插入排序，每次可以让逆序减少的数量>1;

希尔排序使用插入排序对间隔h的序列进行排序，通过不断减小h，最后令h=1，就可以得到整个有序数组

2.复杂度：

时间复杂度：N的若干倍 × 递增序列的长度,达不到平方级别

空间复杂度：O(1)

class Solution5 {       public int[] sortArray(int[] nums) {           int N = nums.length;        int h = 1;        while (h
   
    =1){               for (int i = h; i < nums.length; i++) {                   for (int j = i; j >= h && nums[j]

5.堆排序——不稳定

1.堆中某个节点的值总是大于等于或者小于等于其子节点的值，并且堆是 完全二叉树、

1.堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。

2.位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。

3.这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

2.复杂度：

时间复杂度：NlogN

空间复杂度：1

大顶堆

class Solution {       public int[] sortArray(int[] nums) {           sortHeap(nums);        return nums;    }    1.堆排序    public void sortHeap(int[] arr){           1.先初步建立大顶堆，不管叶子节点        for (int i = (arr.length/2)-1; i >=0 ; i--) {               bigHeapBuid(arr, arr.length, i);        }        for (int i = arr.length-1; i >=0 ; i--) {               swap(arr,0,i); 依次把在下标0处 冒头的 元素揪到后面            bigHeapBuid(arr, i,0);对新换上去的 下标0元素，进行堆整理，确保其为 去顶后的最大值        }    }    //2.构造大顶堆    public void bigHeapBuid(int[] arr,int len,int root){           int largest = root;  假设根节点是最大节点        int left    = 2*root+1;        int right    = 2*root+2;        第一个判断条件,保证左下标不会超过树的全部节点，也就是说不会取到1个 out of index 的节点        if (left
   
    arr[largest])            largest=left;        if (right
    
     arr[largest])            largest=right;        满足这个条件说明，原root不是最大节点，需要进行节点交换，把最大值换上去        if (largest!=root){               swap(arr, largest, root);            因为largest下标所在元素被下来的原root替换了            所以要对其递归，确保换下来的元素 在该分支子树上是最大的            bigHeapBuid(arr, len, largest);         }    }    public void swap(int[] nums,int i,int j){           int temp = nums[i];        nums[i]  = nums[j];        nums[j]  = temp;    }}

小顶堆(大小顶堆区别在于下边的构造函数)

2.构造小顶堆    public void smallHeapBuid(int[] arr,int len,int root){           int lowest = root;  假设根节点是最小节点        int left    = 2*root+1;        int right    = 2*root+2;        第一个判断条件,保证左下标不会超过树的全部节点，也就是说不会取到1个 out of index 的节点        if (left

6.归并排序（基于分治思想）——不是原地排序（需要辅助数组）

1.思想：把数组分成2部分，分别进行排序，然后归并起来

2.时间复杂度：O（Nlog(N)）
空间复杂度：N

3.稳定、效率高，但是比较占内存

重点：

1.merge()函数

2.递推公式

class Solution {       public int[] sortArray(int[] nums) {           sort(nums,0, nums.length-1);        return nums;    }    归并排序递归主体    public void sort(int[] nums,int low,int high){           if (low>=high) return ;        int mid = (low+high)/2;        sort(nums, low, mid);        sort(nums, mid+1, high);        merge(nums,low,mid,high);    }    归并方法,把数组中两个已经排序的部分合成一个    public void merge(int[] nums,int low,int mid,int high){           int nL = mid-low+1,nR = high-mid;        1.建立辅助数组        int[] numsLeft  = new int[nL];        int[] numsRight = new int[nR];        2.给辅助数组赋值，注意下标        for (int k = 0; k < nL; k++) {               numsLeft[k] = nums[low+k];  注意此处nums下标        }        for (int k = 0; k < nR; k++) {               numsRight[k]=nums[mid+1+k]; 注意此处nums下标        }        int i=0,j=0,k=low;        while (i

7.快速排序（不稳定）——是原地排序

1.思想：

归并排序把数组分为2个子数组分别排序，并将有序的子数组归并，使得整个数组排序

快排通过一个切分元素，把数组分为2个子数组，左子数组<=切分元素，右子数组 >=切分元素

也就把两个子数组排序了

2.复杂度

时间复杂度O(Nlog(N)) ，当数组有序时，最坏复杂度：O(N²)

空间复杂度：O(logN)~O(N)

重点：

1.partition() 分割函数

2.递推公式。

class Solution {       public int[] sortArray(int[] nums) {           sort(nums,0, nums.length-1);        return nums;    }    public void sort(int[] nums,int low ,int high){           if (low>=high)return;        1.找出分割基准        int partiti = partition(nums, low, high);        2.递归sort        sort(nums, low, partiti-1);        sort(nums, partiti+1, high);    }    public int partition(int[] nums,int low,int high){           int base = nums[low];   这里选择基准时，如果是low，就要先做从后向前的遍历        //int base = nums[high];   这里选择基准时，如果是high，就要先做从前向后的遍历                int left = low,right=high;        while (left
   
    =号！！！            while (left
    
     =base) right--;  右子数组 >=切分元素！！！            2.后  从前向后遍历 ，这里要注意是>=号！！！              while (left