数据结构笔记---经典排序算法排序

@[toc]

排序的思维导图

排序的思维导图
在这里插入图片描述

排序的时间复杂度

排序的时间复杂度

各种排序的原理

插入排序（Insertion Sort）

算法描述：

在这里插入图片描述

算法实现：

void InsertSort(int  *a, int n) {
    int tmp = 0;
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        if (a[i] < a[j]) {
            tmp = a[i];
            a[i] = a[j];
            while (tmp < a[j-1]) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = tmp;
        }
    }
}

冒泡排序

算法描述：

每一趟排序，都是从第一个元素开始比较，将大的元素（或小的元素往后交换），每次都有一个元素落在最终位置，时间复杂度和初始序列有关

冒泡排序

算法实现

void bubbleSort(int *arr, int n) {
    for (int i = 0; i<n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
        {
            //如果前面的数比后面大，进行交换
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j]; 
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
}

---

快排

算法描述：

在这里插入图片描述

算法实现：

//分治法把数组分成两份
int patition(int *a, int left,int right) {
    int j = left;    //用来遍历数组
    int i = j - 1;    //用来指向小于基准元素的位置
    int key = a[right];    //基准元素
    //从左到右遍历数组，把小于等于基准元素的放到左边，大于基准元素的放到右边
    for (; j < right; ++j) {
        if (a[j] <= key)
            swap(&a[j], &a[++i]);
    }
    //把基准元素放到中间
    swap(&a[right], &a[++i]);
    //返回数组中间位置
    return i;
}
//快速排序
void quickSort(int *a,int left,int right) {
    if (left>=right)
        return;
    int mid = patition(a,left,right);
    quickSort(a, left, mid - 1);
    quickSort(a, mid + 1, right);
}

选择排序

算法描述：每次在未排好序的，序列中找到最小（或最大的），放到序列最前面

在这里插入图片描述

算法实现：

void SelectSort(int *a, int n) {
    for (int i = 0; i < n; i++)
    {
        int key = i;    //    临时变量用于存放数组最小值的位置
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[key]) {    
                key = j;    //    记录数组最小值位置
            }
        }
            if (key != i)
            {
                int tmp = a[key]; a[key] = a[i]; a[i] = tmp;    //    交换最小值
            }
        
    }
}

堆排序

1. 建堆
   从第一个非叶子节点，从右到左，从下到上依次筛选，筛选的依据是在孩子节点中找到，比父节点元素大（小根堆则找小的）
2. 排序
   建堆完成之后，每次删除堆顶元素。删除的依据是将堆顶元素和最底端最右边的叶子节点互换位置，再删除刚刚被调整的叶子节点，之后要做的操作是将根顶元素调整到适当的位置；

---

归并排序

算法描述：

在这里插入图片描述

void Merge(int a[], int left, int mid, int right)
{
    int len = right - left + 1;        //    数组的长度
    int *temp = new int[len];       // 分配个临时数组
    int k = 0;
    int i = left;                   // 前一数组的起始元素
    int j = mid + 1;                // 后一数组的起始元素
    while (i <= mid && j <= right)
    {
        //    选择较小的存入临时数组
        temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];  
    }
    while (i <= mid)
    {
        temp[k++] = a[i++];
    }
    while (j <= right)
    {
        temp[k++] = a[j++];
    }
    for (int k = 0; k < len; k++)
    {
        a[left++] = temp[k];
    }
}

// 递归实现的归并排序
void MergeSort(int a[], int left, int right)  
{
    if (left == right)    
        return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

参考资料：2019年王道数据结构
下载地址：2019年王道操作数据结构