C语言实现数组快速排序算法

灰太狼 2022-08-07 01:59 187阅读 0赞

**C语言实现数组快速排序算法**

快速排序算法，顾名思义，是迄今为止发现的速度最快的排序算法。快速排序算法采用分治的思想，首先在要排序的序列\{5,8,7,6,4,3,9\}中选取一个基准数（一般选取序列的第一个，其实选取哪个是无关紧要的），将序列分成两部分，其中基准数的左边全是小于基准数的数，基准数右边是大于或者等于基准数的数。这样，基准数的位置在序列中的位置就固定了，然后将基准数两边的序列进行相同的处理，直到最后一个序列只有一个数字，这样算法就完成了。图解如下：

序列\{5,8,7,6,4,3,9\}，第一次选取基准数5进行一次划分，划分后的序列为：\{3,4,5,6,8,7,9\}，5左边的序列\{3，4\}进行相同的划分，选取这个序列的基准数为3，划分后的结果为\{3,4\}，此时3的左边已没有序列，而3右边的序列为\{4\}，因为这时序列中只有一个数字，显然这样的序列是已经排好序的；然后处理第一次基准数5右边的序列\{6,8,7,9\}，选取基准数为6，进行划分后序列为\{6,8,7,9\}，6左边已经没有序列，6右边的序列为\{8,7,9\},对这个序列选取基准数为8，进行划分得\{7,8,9\}，8左边和序列为\{7\}，右边的序列为\{9\}，此时，排序已经完成。动态图如下：

![Center][]

可见，快速排序的核心算法就是划分算法，在我们上面的讨论中，这种划分算法是由Glenn W. Rowe提出的，还有一种更早的划分算法是由C. A. R. Hoare提出的。这里只讨论和实现Glenn W. Rowe提出的划分算法。快速排序算法的运行过程如下：  
开始——划分序列——得到划分序列的子序列——再次划分——得到划分序列的子序列……。  
首先讨论Glenn W. Rowe划分算法：  
假如Glenn W. Rowe划分算法选取数组第0位作为基准数，那么Glenn W. Rowe划分算法从数组第1位扫描到数组最后一位，遇到比基准数大的，就交换到右边，比基准数小的，交换到左边，其算法时间复杂度为O(n)  
实现代码如下：

//采用Glenn W. Rowe划分算法
    int partition_Rowe(int arr[], int low, int high)
    {//根据一个基准数，将数组分为基准数左边小于基准数，基准数右边大于或等于基准数的两部分
    //返回值是基准数在数组中的下标
    //这里选取数组元素的第0位作为基准数
    //low为最低下标，high为最高下标
    int pivot = arr[low];//选取基准数
    int low_index = low;
    for (int i = low + 1; i <= high; i++)
    {
    if (arr[i] < pivot)
    {
    //在序列中找到一个比pivot小的，就递增low_index
    low_index++;
    if (i!=low_index)//如果i和low_index相等，则在i之前都不存在需要交换的比pivot大的数
    {
    swap(arr, i, low_index);
    }
    }
    }
    //low_index的位置就是pivot应处在的位置，low_index指向的总是比pivot小的数
    arr[low] = arr[low_index];
    arr[low_index] = pivot;
    return low_index;
    }

以序列\{5,8,7,6,4,3,9\}为例，一次划分过程如下：  
1. low\_index首先指向基准数，循环从数组第1位开始：  
  ![Center 1][]  
2. 如果在遍历部分的元素中发现比基准数更小的数，则自增low\_index，判断遍历的下标i与low\_index是否相等，若不相等，则交换i和low\_index指向的元素，若相等，则说明low\_index指向的元素比基准数要小。在上面的序列中，i指向的8,7,6都要比基准数大，low\_index不会发生自增行为，直到i指向4进，4要比基准数5小，low\_index自增，此时low\_index指向8，i和low\_index并不相等，于是交换两个元素的位置，如此类推，3和7的位置交换。循环结束，low\_index指向的元素为3，交换3和5的元素位置，一次划分完成。  
  ![Center 2][]  
最后为：  
  ![Center 3][]  
此时，基准数左边的数全是小于基准数的，右边的数全是大于或者等于基准数的。快速排序的思想是将基准数左边与右边分成2个序列，重复此过程，直到最后每个序列只有一个元素，则数组就已经排好序了。  
快速排序的实现代码如下：

void quick_sort(int arr[], int low, int high)
    {
    if (high > low)//如果需要排序的序列的元素个数大于1
    {
    int pivot_pos = partition_Rowe(arr, low, high);
    quick_sort(arr, low, pivot_pos - 1);//左序列
    quick_sort(arr, pivot_pos + 1, high);//右序列
    }
    }

用于交换数组两个元素的函数声明如下：

void swap(int arr[], int index_i, int index_j)
    {//将数组相应位置的两个数相交换
    int k = arr[index_i];
    arr[index_i] = arr[index_j];
    arr[index_j] = k;
    }

测试代码如下：

int main()
    {
    int arr[] = {5,8,7,6,4,3,9};
    for (int i = 0; i < 7; i++)
    {
    printf("%d,", arr[i]);
    
    
    }
    printf("\n");
    quick_sort(arr, 0, 6);
    for (int i = 0; i < 7; i++)
    {
    printf("%d,",arr[i]);
    
    }
    return 0;
    }

输出结果为:

![Center 4][]

[Center]: /images/20220805/24bee3c0b86e488f9b2f6542196d45a4.png
[Center 1]: /images/20220805/6ff225655f0247948477e47d44ec750b.png
[Center 2]: /images/20220805/d4c1740e80204c89a191ebd7dcc0e03a.png
[Center 3]: /images/20220805/b8587a2b3a3e4aab8f6362803a75dbec.png
[Center 4]: /images/20220805/2f3d9ecebf2d4f8190abee0f8a6e3e2b.png