排序

基本概念

评价指标：

1. 稳定性：关键字相同的元素在排序后相对位置不变，但是稳定的算法一定比不稳定的好？不一定，要看实际需求

2. 复杂度：

   1. 时间复杂度
   2. 空间复杂度

分类：

1. 内部排序：关注如何使算法时间空间复杂度更低
2. 外部排序： 还需要关注如何使读写磁盘次数更少

内部排序

1. 插入类排序：

   1. 直接插入排序
   2. 折半插入排序
   3. 希尔排序

2. 交换排序

   1. 冒泡排序
   2. 快速排序

3. 选择排序

   1. 简单选择排序
   2. 堆排序
4. 归并排序
5. 基数排序

外部排序

快速排序

排序思路过程

1.一开始第一个元素即默认为基准，但也是low

2.基准左面的都比基准小，基准右侧都比基准大，因此两侧扫描的时候只有符合条件的才会换过去，相等的就是不动，所以是一个不稳定的算法。

3.当low>=high就换，而且基准是和low换

算法图解

代码实现（C语言）

#include <stdio.h>
int Partition(int* arr, int low, int high)
{
    //一次划分
    int tmp = arr[low];//基准
    while (low < high)
    {
        //（1）从后往前找比基准小的数字
        while (low<high && arr[high]>tmp)
        {
            high--;
        }
        if (low < high)
        {
            arr[low] = arr[high];
        }
        //（2）从前往后找比基准大的数字
        while (low < high && arr[low] <= tmp)
        {
            low++;
        }
        if (low < high)
        {
            arr[high] = arr[low];
        }
    }
    arr[low] = tmp;
    return low;
}
void Quick(int* arr, int low, int high)
{
    int par = Partition(arr,low, high);
    if (low < par - 1)//左边数据超过一个
    {
        Quick(arr, low, par - 1);
    }
    if (par + 1 < high)//右边数据超过一个
    {
        Quick(arr, par + 1, high);
    }
}
void QuickSort(int* arr, int len)
{
    Quick(arr, 0, len - 1);//参数一致
}
void Show(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

代码思路总结：

1. 从后往前找比基准小的数据，往前挪
2. 从前往后找比基准大的数据，往后挪
3. 重复第一步和第二步。

快速排序性能

快速排序是所有内部排序算法中平均性能最优的排序算法

关键点

1. 一趟排序可以确定一个元素的最终位置。
2. 要求快排的速度快，理想状况就是每次基准都可以把表划分成两个长度相近的子表，此时速度是最快的。当表本身是有序的或者逆序的此时快拍的速度是最慢的。
3. 快速排序本质上是一种交换排序。

思路过程

对待排序序列进行扫描，每次对一对元素排序，最终一轮扫描会将一个最大的元素移动到末尾，过程像冒泡，所以称之为冒泡排序。

算法图解

代码实现（c语言）

#include<stdio.h>
void sort(int arr[], int size)
{
    int j,i,tem;
    for (i = 0; i < size-1;i ++)//size-1是因为不用与自己比较，所以比的数就少一个
    {
        int count = 0;
        for (j = 0; j < size-1 - i; j++)    //size-1-i是因为每一趟就会少一个数比较
        {
            if (arr[j] > arr[j+1])//这是升序排法，前一个数和后一个数比较，如果前数大则与后一个数换位置
            {
                tem = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tem;
                count = 1;
                
            }
        }
        if (count == 0)            //如果某一趟没有交换位置，则说明已经排好序，直接退出循环
                break;    
    }
 
}

实战演练

题目链接：剑指 Offer II 077. 链表排序

代码实现：

struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != NULL) {
        temp->next = temp1;
    } else if (temp2 != NULL) {
        temp->next = temp2;
    }
    return dummyHead->next;
}

struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {
    if (head == NULL) {
        return head;
    }
    if (head->next == tail) {
        head->next = NULL;
        return head;
    }
    struct ListNode *slow = head, *fast = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    struct ListNode* mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));
}

struct ListNode* sortList(struct ListNode* head) {
    return toSortList(head, NULL);
}