数据结构|排序算法（一）快速排序

一、排序概念

排序是数据结构中的一个重要概念，它是指将一组数据元素按照特定的顺序进行排列的过程，默认是从小到大排序。

常见的八大排序算法：

插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序

二、快速排序（重点常考）

1.算法思想：

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2.算法步骤：

1.选择一个基准值（通常选择序列的第一个元素或最后一个元素）。
2.从序列的两端开始，设置两个指针，一个指向序列的起始位置（left），一个指向序列的结束位置（right）。
3.从 right 指针开始，向左移动 right 指针，找到第一个小于基准值的元素，（从后往前找，找比基准小的数字，往前挪），然后从 left 指针开始，向右移动 left 指针，找到第一个大于基准值的元素（从前往后找，找比基准大的数字，往后挪）。
4.交换 left 和 right 指针所指向的元素。
5.重复步骤 3 和 4，直到 left 和 right 指针相遇。此时，将基准值与 left 指针所指向的元素交换位置，这样基准值就处于正确的排序位置上，并且其左边的元素都小于它，右边的元素都大于它。（完成快速排序的一次划分）
6.对基准值左边和右边的子序列分别重复步骤 1 到 5，直到子序列的长度为 1 或 0，此时整个序列就已经有序。

3.代码实现：

//代码实现
#include<stdio.h>
int Partition(int* arr, int left, int right)//一次划分
{int tmp = arr[left];//基准while (left < right){//从后往前找比基准小的数字，往前移动while (left<right&&arr[right] > tmp){right--;}if (left < right)//判断循环出口条件{arr[left] = arr[right];}//从前往后找比基准大的数字，往后移动while (left < right && arr[left] <= tmp){left++;}if (left < right){arr[right] = arr[left];}}arr[left] = tmp;return left;
}
void Quick(int* arr, int left, int right)//递归调用一次划分
{int par = Partition(arr, left, right);if(left<par-1)//左边序列长大于1{Quick(arr, left, par - 1);}if (par + 1 < right)//右边序列长大于1{Quick(arr, par+1, right);}
}
void QuickSort(int* arr, int len)//快速排序
{Quick(arr, 0, len - 1);
}
void Show(int *arr, int size) 
{for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}

4.复杂度分析

5.快速排序特点

优点：平均时间复杂度；不需要额外的存储空间，高效使用内存。

缺点：不稳定，空间复杂度大 ；越有序越慢，完全有序时间复杂度为O(n^2)。

以上是排序算法第一部分关于快速排序的知识，如果有帮助可以点赞收藏一下，会持续更新输出有用的内容，感兴趣可以关注我！