Leetcode 排序类题目排序算法总结

1. Merge Sorted Array

Description： Easy

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Analysis

把两个有序的数组融合到一起，使融合后的数组仍然有序。并且数组1的长度是足够容纳数组2的。
数组1长度长于数组2，说明我们可以在数组1上进行尾插入排序。
3.3个尾指针，第一个判断条件是两个尾指针都没结束。第二个判断条件是短的没结束（ib>=0)，只需要把剩余短的依次插入即可。
4.其实还有第三个判断，长的没结束，但是此时由于我们在长的上操作的，所以不需要任何操作，数组是有序的。

Solution 混合尾插入排序

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
      // l1和l2分别是nums1和nums2当前比较的指针，lcur是当前插入位置
      int l1 = m-1, l2 = n-1, lcur = m+n-1;
      // 一直比较，直到1或2有一个到头，2先到头无所谓，正好结束
      while(l1 >= 0 && l2 >=0){
        // 注意后置--++
        nums1[lcur--] = nums1[l1] >= nums2[l2] ? nums1[l1--] : nums2[l2--];
      }
      // 1先到头单独考虑，把nums2剩余的插入前面
      while(l2 >= 0){
        nums1[lcur--] = nums2[l2--];
      }  
    }
};

tips
1.两个判断条件 while(ia>=0 && ib>=0); while(ib>=0)
2.三元运算符 A[icur--] = A[ia]>=B[ib] ? A[ia--]:B[ib--]

2. Merge Two Sorted Lists

Description： Easy

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Analysis

合并两个有序的链表。
新建一个链表，比较原始两个链表，开始插入。只要两者有一个为空，则把剩余的全部插入。

Solution

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 创建一个新链表，并使用一个指针指向该链表
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        // 只要两个链表一个不为空
        while(l1 && l2)
        {
            // 一次比较插入排序
            if(l1->val<=l2->val)
            {
                cur->next = l1;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                l2 = l2->next;
            }
            // 一次比较插入需要更新cur
            cur = cur->next;
        }
        
        // 只要有一个为空，只需要把剩下的节点直接全部插入
        cur->next = l1?l1:l2;
        
        return dummy->next;
    }
};

tips

新建链表 ListNode *dummy = new ListNode(-1), 头节点是dummy
判断链表是否为空，if(l1)

3. Insertion Sort List

Description：

对两个链表进行直接插入排序

Analysis

遍历链表，一个个插入，使链表逐渐有序
发现当前有序链表插入位置是关键

Solution


class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        // 新建链表的头节点
        ListNode *dummy = new ListNode(-1);
        // 遍历链表，建立新链表
        for(ListNode *cur = head; cur!=nullptr;)
        {
            ListNode* pos = FindInsertPos(dummy, cur->val);
            ListNode *temp = cur->next;
            cur->next = pos->next;
            pos->next = cur;
            cur = temp;
        }
        return dummy->next;
        
    }
    
    // 定义找到当前有序链表内插入一个数的位置
    ListNode* FindInsertPos(ListNode *head, int x)
    {
        // 定义一个链表节点表示插入位置的前一个节点，因为链表只能返回next
        ListNode *pre = nullptr;
        // 遍历当前有序链表, 遍历都需要新建一个链表节点
        for(ListNode *cur = head; cur!=nullptr && cur->val<x; pre = cur, cur = cur->next)
            ;
        return pre;
    }
};

tips

遍历链表需要建立新节点 for(ListNode *cur = head; cur!=nullptr;cur = cur->next)

4. Sort List

Description： Medium

Sort a linked list in O(n log n) time using constant space complexity.
Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Analysis

1.以常数空间，nlogn时间复杂度完成一个无序链表的排序。
2.单链表使用归并排序，双向链表使用快速排序。

Solution:

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        //使用快慢指针，找到链表中间节点
        ListNode *fast = head, *slow = head;
        if(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 断开两段
        fast = slow;
        slow = slow->next;
        fast->next = NULL;
        // 递归，利用本函数继续对两个分支排序
        ListNode *l1 = sortList(head);
        ListNode *l2 = sortList(slow);
        // 经过上面操作后，认为两个分支是有序的，使用之前的合并两个有序链表的函数
        return MergeTwoSortedLists(l1, l2);
    }
    ListNode* MergeTwoSortedLists(ListNode *l1, ListNode *l2)
    {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        while(l1 && l2)
        {
            if(l1->val<=l2->val)
            {
                cur->next = l1;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1?l1:l2;
        return dummy->next;
    }
};

tips

使用快慢指针找到链表中间节点的方式。
归并排序使用递归实现。
归并排序前提，合并两个有序链表。

一下都是搜集的网上的知识，并不是我的原创，收集来学习使用。

各类排序算法复杂度

时间复杂度

平均情况下：快(快速排序)些(希尔排序)以“nlogn”的速度归(归并排序)队(堆排序)！其它n^2
最坏情况下：快速排序n^2，其他和平均情况一样。

空间复杂度

快速排序logn
归并排序n
其它1

稳定性
快(快速排序)些(希尔排序)选(简单选择)一堆(堆排序)好友聊天！（不稳定）

各类排序算法总结实现

插入排序

基本思想：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止。
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经
排好序
此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
元素集合越接近有序，直接插入排序算法的时间效率越高 .如果对于最初的数据是倒序排列的，则每次比较都需要移动数据，导致算法效率降低
最优情况下：时间效率为O(n)
最差情况下：时间复杂度为O( n^2)
空间复杂度：O(1)
它是一种稳定的排序算法

template <typename T>
void InsertSort(vector<T>& array)
{
    for(int i=0; i<array.size(); ++i)
    {
        for(int j=i; j>0; --j)
        {
            if(array[j] < array[j-1])
                swap(array[j], array[j-1]);
            else
                break;
        }
    }
}

public void insertSort(int[] A) {
        int len = A.length;
        int j;
        for(int i=0;i<len;i++){
            int tmp = A[i];
            for(j = i; j > 0 && tmp < A[j-1]; j--)   
                A[j] = A[j-1];   
            A[j] = tmp;
        }
    }

希尔排序

缩小增量排序，是对直接插入排序的优化
相当于以不断变小的增量划分子序列，对原数据进行预排序,通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序。
不需要大量的辅助空间
希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，而快速排序在最坏的情况下执行的效率会非常差。

void shellSort(myDataType *ary,int len)
{
    int i,j;
    int increment = len;//增量
    myDataType key;
    while(increment > 1)//最后在增量为1并且是执行了情况下停止。
    {
        increment = increment/3 + 1;//根据公式
        //printf("increment:%d\n",increment);
        for (i=increment;i<len;i++)//从[0]开始，对相距增量步长的元素集合进行修改。
        {
            key = ary[i];
            //以下和直接插入排序类似。
            j=i-increment;
            while(j >= 0)
            {
                if (key < ary[j] )
                {
                    myDataType temp = ary[j];
                    ary[j] = key;
                    ary[j+increment] = temp;
                }
                j=j-increment;
            }
        }
    }
}

冒泡排序

相邻数值两两交换。从第一个数值开始，如果相邻两个数的排列顺序与我们的期望不同，则将两个数的位置进行交换（对调）；如果其与我们的期望一致，则不用交换。
一趟冒泡排序，最大（小）的到达末尾
结束标志：一趟排序没有发生任何元素交换
一般地，如果有N个数需要排序，则需要进行（N-1）趟起泡
最好情况O(n)，最差情况O(n^2)

  public void bubbleSort(int[] A) {
        int len = A.length;
        for(int i=0; i<len;i++) {
            for(int j=len-1; j>i; j--) {
                if(A[i]>A[j]){
                    int tmp = A[i];
                    A[i] = A[j];
                    A[j] = tmp;
                }
            }
        }
    }

堆排序

首先对数组中所有的元素建立一个最小堆，然后依次推出栈顶的元素（最小的），重新建堆。直到堆中的元素为空。
堆排序为原位排序，空间复杂度小，时间复杂度为O(n log n)

public void heapSort(int[] array) {  
            if (array == null || array.length <= 1) {  
                return;  
            }  

            buildMaxHeap(array);  

            for (int i = array.length - 1; i >= 1; i--) {  
                swap(array, 0, i);  

                maxHeap(array, i, 0);  
            }  
        }  

        private void buildMaxHeap(int[] array) {  
            if (array == null || array.length <= 1) {  
                return;  
            }  

            int half = array.length / 2;  
            for (int i = half; i >= 0; i--) {  
                maxHeap(array, array.length, i);  
            }  
        }  

        private void maxHeap(int[] array, int heapSize, int index) {  
            int left = index * 2 + 1;  
            int right = index * 2 + 2;  

            int largest = index;  
            if (left < heapSize && array[left] > array[index]) {  
                largest = left;  
            }  

            if (right < heapSize && array[right] > array[largest]) {  
                largest = right;  
            }  

            if (index != largest) {  
                swap(array, index, largest);  

                maxHeap(array, heapSize, largest);  
            }  
        }

归并排序

归并排序是一种分治策略，该算法采用经典的分治（divide-and-conquer）策略，分治法将问题分(divide)成一些小的问题然后递归求解
最终分成n个序列（只有一个所以有序），所以空间复杂度为n
时间复杂度nlogn
关键是归并操作：将两个有序序列合并成一个有序序列

public void mergeSort(int[] A,int l,int r) {
        if(l>=r) return; 
            int m = l + (r-l)/2;
            mergeSort(A,l,m);
            mergeSort(A,m+1,r);
            merge(A,l,m,r);

    }

    public void merge(int[] A, int l, int mid, int r) {
        int[] B = new int[A.length];
        int s = l;
        int m = mid+1;
        int k = l;//数组标志位
        while(s<=mid && m<=r) {
            if(A[s]<=A[m]) {
                B[k++] = A[s++];
            } else{
                B[k++] = A[m++];
            }
        }
        while(s<=mid) {
            B[k++] = A[s++];
        }
        while(m<=r) {
            B[k++] = A[m++];
        }

        for(int i=l;i<=r;i++) {
            A[i] = B[i];
        }
    }

快速排序

1.首先从数组中选择一个数字X，然后用首尾指针将大于X的放在数组的右边，小于X的放在数组左边，这样在X的左边的数字全部为小于X的数字，在X右边的数字全部为大于X的数字。对于数字X，它的位置已经确定；

然后将X左边和X右边依次递归进行这样的过程，最后得到的数字即为有序
最终的序列以枢纽为中心，左边比其小，右边比其大。
取数组中的中位数（实际上采用三数中值分割的方法），会将递归的层数减少(每次少一半，)，使复杂度趋近N*log(N);
如果每次选取的数字为待排序部分中，最小或最大的，会加大递归层数(每次少1), 复杂度趋近 N*N
所以如果取第一个数为枢纽：序列基本有序和序列长度较短时，不建议使用快速排序。

public void quickSort(int[] A, int l, int r) {
        if(l<r) {
            int p = partition(A,l,r);
            quickSort(A,l,p-1);
            quickSort(A,p+1,r);
        }

    }

    public int partition(int[] A, int l, int r) {
        int tmp = A[r];
        int p = l-1;
        for(int i=l; i<r;i++) {
            if(A[i]<=tmp) {
                p++;
                swap(A,p,i);
            }
        }
        p++;
        swap(A,p,r);
        return p;
    }

计数排序(桶排序)

时间复杂度O（n），空间复杂度O（k），k是输入序列的值的范围（最大值-最小值），是稳定的。
计数排序一般用于已知输入值的范围相对较小，比如给公司员工的身高体重信息排序。
假设n个输入元素中的每一个都是介于0到k之间的整数，对每一个输入元素x，确定出小于x的元素个数，有了这一信息，就可以把x直接放在它在最终输出数组的位置上，例如，如果有17个元素小于x，则x就是属于第18个输出位置。
举个例子，假设输入数组A为{3，5，1，2，4，3}，值的范围是1~5，所以创建5个桶，序号1，2，3，4，5。装桶时遍历一遍输入数组，A[0]=3，把它放到3号桶；A[1]=5，放到5号桶；1放到1号桶……最后3放到3号桶。现在三号桶的值为2，其他桶的值为1，再遍历一遍桶数组，按顺序把桶倒出，元素被倒出的顺序就是排序的顺序了。

public class CountingSort {
    public int[] countingSort(int[] A, int n) {
        //找数组中的最大值和最小值，确定桶的个数
        int max=A[0];
        int min=A[0];
        for(int i=0;i<n;i++){
            if(A[i]>max)
                max=A[i];
            if(A[i]<min)
                min=A[i];
        }
        //定义桶数组B并初始化
        int[] B= new int[max-min+1];
        for(int i=0;i<max-min+1;i++)
            B[i]=0;
        //把数组A的元素装到对应桶里
        for(int i=0;i<n;i++){
            B[A[i]-min]++;
        }
        //把所有桶倒出来
        for(int i=0,j=0;j<max-min+1;j++){
            //倒桶j
            for(int k=B[j];k>0;k--){
                A[i++]=j+min;
            }
        }
        return A;
    }
}

各类面试题目

nlogn的指的快排，归并排序，堆排序。
序列基本有序：直接插入，堆
请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。给定一个int数组A及它的大小n，请返回它是否有重复值。

计数排序，简单高效。实际上如果没有额外空间复杂度的限制
用哈希表遍历一般数组，记录数值出现次数

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。

首先想到的满足它时间复杂度要求的解决方案就是使用计数排序，因为他要复杂度为O(n),用桶排序思想实现。先装桶，再遍历一遍桶，计算非空桶序号最大差值。

Leetcode 排序类题目 排序算法总结

1. Merge Sorted Array

Description： Easy

Analysis

Solution 混合尾插入排序

2. Merge Two Sorted Lists

Description： Easy

Analysis

Solution

3. Insertion Sort List

Description：

Analysis

Solution

4. Sort List

Description： Medium

Analysis

Solution:

各类排序算法复杂度

各类排序算法总结实现

插入排序

希尔排序

冒泡排序

堆排序

归并排序

快速排序

计数排序(桶排序)

各类面试题目

Leetcode 排序类题目排序算法总结