C语言实现数组快速排序算法-蒲公英云

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

灰太狼 2022-08-07 01:59 256阅读 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}为例，一次划分过程如下：

low_index首先指向基准数，循环从数组第1位开始：
如果在遍历部分的元素中发现比基准数更小的数，则自增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的元素位置，一次划分完成。

最后为：

此时，基准数左边的数全是小于基准数的，右边的数全是大于或者等于基准数的。快速排序的思想是将基准数左边与右边分成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;
}