C语言排序之快速排序

       快速排序是一种高效的排序算法。它采用了分治的策略，通过选择一个基准元素，将待排序的序列划分为两部分，一部分的元素都比基准元素小，另一部分的元素都比基准元素大，然后对这两部分分别进行快速排序，从而实现整个序列的有序排列。

以下是快速排序的基本步骤：

1. 选择一个基准元素：通常可以选择序列的第一个元素、最后一个元素或者中间元素作为基准。
2. 分区操作：通过一系列的比较和交换，将序列中小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。
3. 对分区后的左右两部分子序列，分别重复步骤 1 和 2，直到整个序列有序。

例如，对于序列 [12, 11, 13, 5, 6] ，选择第一个元素 12 作为基准：

• 经过分区操作后，序列变为 [5, 11, 6, 12, 13] 。
• 然后对 [5, 11, 6] 和 [12, 13] 分别继续进行快速排序。

快速排序的平均时间复杂度为 （O（nlogn）） ，空间复杂度为（Ologn）  。在大多数情况下，它的性能非常出色，但在最坏情况下，时间复杂度会退化为(On2)  。不过，通过合理选择基准元素，可以很大程度上避免最坏情况的发生。

快速排序的单趟排序

       通过一趟排序将数据分割成独立的两部分，其中一部分的所有数据都比另一组数据的数值小，然后再次使用相同的方法分别将这两部分再分成两部分，从而完成快速排序。

1.霍尔法

“霍尔法”通常指的是快速排序（Quick Sort）中的一种实现方式，也被称为霍尔划分。

快速排序是一种分治算法，其基本思想是通过一趟排序将待排序的序列划分成两部分，然后对这两部分分别进行排序，以实现整个序列的有序。

霍尔法的具体实现步骤如下：

1. 选取一个基准元素 key，通常选择数组的第一个元素、中间元素或最后一个元素，也可以选择这三个元素的中间值等，然后将这个基准元素与数组第一个元素进行交换。
2. 定义两个指针 left 和 right，left 从数组的第一个元素开始（即左边）向右遍历，right 从数组的最后一个元素开始（即右边）向左遍历。
3. 首先，right 指针从右向左移动，找到比 key 小的值时停下来。然后，left 指针从左向右移动，找到比 key 大的值时停下来。
4. 交换 left 和 right 所指向的值，这一步的目的是将比 key 小的值往左放，将比 key 大的值往右放。
5. 重复步骤 3 和 4，直到 left 和 right 相遇。
6. 当 left 和 right 相遇后，将第一个元素（即 key）与它们相遇位置的值交换。此时，key 左边的元素都比它小，右边的元素都比它大，但左右两边的子序列并不一定是有序的。
7. 对 key 左边的子序列和右边的子序列，分别重复上述步骤，进行递归排序，直到子序列不存在或者只有一个元素时结束递归。

key——>基准下标值；

指针 left指向最左端的元素也就是第一个元素（找比key大的元素）

        right指向最右端的元素也就是最后一个元素（找比key小的元素）

<1>

      left记录左下标，从左向右遍历

      right记录右下标，从右向左遍历，以第一个数作为基准值

<2>

      right先出发，找比key小的值，找到停下

<3>

      left出发，找比key大的值，找到停下并与right进行交换

<4>

     重复步骤<2>,<3>,直到left与right指向同一个数

<5>

    将left/right与key交换，完成单趟排序

总的来说就是把比key小的放在key左边，比key大的放在key右边，以下是代码实现单趟排序

#include <stdio.h>

// 交换两个整数的值
void swap(int* a, int* b) {
    int tmp = 0;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

// 获取数组中 begin、mid、end 三个位置元素的中间值，并与数组第一个元素交换
int getMid(int* a, int begin, int end) {
    int mid = (begin + end) / 2;
    if (a[begin] > a[mid]) {
        if (a[mid] > a[end]) {
            return mid;
        } else if (a[end] > a[begin]) {
            return begin;
        } else {
            return end;
        }
    } else {
        if (a[begin] > a[end]) {
            return begin;
        } else if (a[end] > a[mid]) {
            return mid;
        } else {
            return end;
        }
    }
}

// 霍尔法快速排序的核心函数
void quickSortHoare(int* a, int begin, int end) {
    int left = begin;
    int right = end;
    if (left >= right) {
        return;
    }
    int mid = getMid(a, begin, end);
    swap(&a[begin], &a[mid]); 
    int keyi = begin; 
    while (left < right) {
        while (left < right && a[right] >= a[keyi]) {
            right--;
        }
        while (left < right && a[left] < a[keyi]) {
            left++;
        }
        swap(&a[left], &a[right]);
    }
    swap(&a[left], &a[keyi]); 
    keyi = left; 
    quickSortHoare(a, begin, keyi - 1); 
    quickSortHoare(a, keyi + 1, end); 
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组为：");
    printArray(arr, n);

    quickSortHoare(arr, 0, n - 1); 

    printf("排序后的数组为：");
    printArray(arr, n);

    return 0;
}

2.挖坑法

        与霍尔法不同的是，将key基准值用变量保存起来，然后将key空出来，也就是形成一个坑，left先指向这个坑right找比key小的值放进坑里，并将自己的位置设为坑，left找比key大的放进坑里，自己又变成坑，如此循环。

<1>

     先定义变量key，存储数组第一个值作为key，此时left指向坑

<2>

     right开始找比key小的数，放进坑里，自己变为坑

<3>

     left开始找比key大的数，同上

<4>

     重复步骤<2>,<3>,直到left与right相遇

<5>

     将key放在相遇的坑里，排序完毕，将key下标返回

以下是代码实现：

int PartSort(int *arr,int left,int right){
int key=arr[left];
int hole=left;
while(left<right){
while(arr[right]>=key&&left<right){
right--;
}
arr[hole]=arr[right];
hole=right;
while(left<right&&arr[left]<=key){
left++;
}
arr[hole]=arr[left];
hole=left;
}
arr[hole]=key;
return hole;
}

 3.前后指针

       将数组的第一个元素作为基准值key，定义前指针prev指向数组第一个元素，后指针cur指向数组第二个数，由cur遍历数组，找出比key小的数，prev在cur找到后向后移动一位并与cur交换，保证较小数在prev之前。

<1>

开始时prev指向数组第一个元素，cur指向第二个元素，此时cur的值比key小，prev向后移动一位后与cur交换，无变化

<2>

cur找到比key大的数此时cur继续向后移动，prev不变

<3>

cur找到比key小的数此时prev向后移动一位，并与cur交换

<4>

     重复步骤<2>,<3>，直到cur完成遍历

                                        交换3和7

                                       交换4和7

<5>

     cur完成遍历后，将prev与key进行交换，返回key的下标

 以下是代码实现：

int PastSort(int *arr,int  left,int right){
int key=left;
int prev=left;
int cur=left+1;
while(cur<=right){
if(arr[cur]<=arr[key]&&++prev!=cur){
swap(&arr[cur],&arr[prev];
}
cur++;
}
swap(&arr[key],&arr[prev]);
return prev;
}

 其实快速排序最核心的代码就是单趟排序，以上三种是单趟排序的三种方法，大家任选一种牢记就好，主要函数的代码如下（递归实现）

void QuickSort(int *arr,int begin,int end){
if(begin>=end){
return;
}
int key=PartSort(arr,begin,end);
QuickSort(arr,begin,key-1);
QuickSort(arr,key+1,end);
}