1.算法介绍
快速排序算法是一种高效排序算法，效率相比普通排序算法较高，通常情况下时间复杂度为O(nlog n)，但在最坏情况下时间复杂度会提高到O(n^2)
2.算法思想和大致步骤
快速排序算法主要用到了二分和递归的思想，主要有三个步骤：（1）在数组中选取一个元素作为基准值(pivot)；（2）将基准值与数组中的剩余数值进行比较，比基准值大的放置于基准值的右边数组，比基准值小的放置于左边数组；（3）将基准值的左右两边分为两个数组，分别对这两个数组递归执行上述操作，直到数组不可再分；最后可以得到处理好的数组
3.算法详细步骤以及代码演示
step1:
生成三个随机数组，长度分别为5,10,100，用作后续的排序
int array5[5];
int array10[10];
int array100[100];
int i,j,k;
printf("array5:\n");
for(i=0;i<5;i++){
array5[i] = rand()%1000000000;
printf("%d ", array5[i]);
printf("\n");
}
printf("array10:\n");
for(j=0;j<10;j++){
array10[j]=rand()%100000000;
printf("%d ", array10[j]);
printf("\n");
}
printf("array100:\n");
for(k=0;k<100;k++){
array100[k]=rand()%1000000000;
printf("%d ", array100[k]);
printf("\n");
}step2:
开始编写排序模块，这里我选择将排序模块分为quick(),quicksoft()函数。quicksoft()函数接收我们之前随机生成的数组以及该数组的最左(left)最右指针(right)。在函数中，我们定义数组的最左指针为基准值，要注意，定义完基准值后，我们要将left指向的基准值暂时提取出数组，此时left指针指向的数组位置为空，为后续指针所指向的数值额度移动做准备。理解并完成上述步骤后就可以开始后续的排序了：由于left指针指向的为空数组，所以我们现在需要移动right指针，此时right指针指向的为数组最后一个元素，假设该指针指向元素比pivot小，按照算法思想，我们需要将改数值放置于基准值的左边，现在我们可以发现，在数组的最右边存在一个空位可以存放我们需要移动的数值，将该数值移动至左边的空值后，right指针指向的位置也空出来了，此时，将left指针往右移动一位，假设现在left指针指向的数值比pivot大，按照算法思想需要存放于pivot的右边，此时我们发现现在right指向的位置为空，将该数值存放于此，并将right指针的位置向左移动一位；后续的步骤以此类推，直到left指针right指针指向同一个位置，会发现该位置为一个空为，将pivot存放于该处，这样就完成了第一次的排序，返回此时的pivot。
代码示例：
int quicksort(int arr[],int left,int right){
int pivot = arr[left];//定义pivot(初始值)
while (right>left)//判断该数组是否能进行排序
{
while (right>left && arr[right]<pivot)//当右指针指向的数值小于pivot时
{
right--;//指针向左移动一位
}
arr[left]=arr[right];//将right指向的值赋予left指针指向的空位
while (right>left && arr[left]>pivot)//当左指针指向的数值小大于pivot时
{
left++;//指针向右移动一位
}
arr[right]=arr[left];将left指向的值赋予right指针指向的空位
}
arr[right]=pivot;//此时left，right指针指向同一个空位，存放pivot
return right;
}编写quick()函数，此函数接收数组，最左最右指针，并将该数组经过quicksoft()函数排序后的分为从pivot分为左右两部分，将左，右数组分别进行递归，直到无法再继续分割递归，此时数组已经排序完成
代码示例：
void quick(int arr[],int left,int right){
if(right>left)//判断是否可以继续递归
{
int pi = quicksort(arr,left,right);//将数组进行初步排序，获取pivot值
quick(arr,left ,pi);//将piv左边的数组进行递归排序
quick(arr,pi+1,right);//将piv右边的数组进行递归排序
}
}step3：
输出排序后的数组
void printarray(int arr[],int size){
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}我们就可以得到排序好的数组了。
完整代码示例：
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
int quicksort(int arr[],int left,int right){
int pivot = arr[left];
while (right>left)
{
while (right>left && arr[right]<pivot)
{
right--;
}
arr[left]=arr[right];
while (right>left && arr[left]>pivot)
{
arr[right]=arr[left];
left++;
}
arr[right]=arr[left];
}
arr[right]=pivot;
return right;
}
void quick(int arr[],int left,int right){
if(right>left)
{
int pi = quicksort(arr,left,right);
quick(arr,left ,pi);
quick(arr,pi+1,right);
}
}
void printarray(int arr[],int size){
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main(){
srand(time(NULL));
int array5[5];
int array10[10];
int array100[100];
int i,j,k;
printf("array5:\n");
for(i=0;i<5;i++){
array5[i] = rand()%1000000000;
printf("%d ", array5[i]);
printf("\n");
}
printf("array10:\n");
for(j=0;j<10;j++){
array10[j]=rand()%100000000;
printf("%d ", array10[j]);
printf("\n");
}
printf("array100:\n");
for(k=0;k<100;k++){
array100[k]=rand()%1000000000;
printf("%d ", array100[k]);
printf("\n");
}
printf("quicknewarray5:");
printf("\n");
quick(array5,0,5);
printarray(array5,5);
printf("\n");
printf("quicknewarray10:");
printf("\n");
quick(array10,0,10);
printarray(array10,10);
printf("\n");
printf("quicknewarray100:");
printf("\n");
quick(array100,0,100);
printarray(array100,100);
printf("\n");
}
交流学习可联系：[email protected]
标签：arr,right,int,学习,算法,数组,pivot,排序,left From： https://blog.csdn.net/weixin_74390075/article/details/143660295