快速排序的基本思路就是选择一个基数.(我们这个基数的选择都是每一组最左边的数) 然后排成: **1.**基数左边都是不大于它的,左边都是不小于它的 **2.**然后左边、右边继续进行这个基本思路 以完成排序作为最后的结束
以6个数为一个例子吧! 4,2 ,6,3,1,5 第一步:确定一个基数,以每次排序最左边的数为基数。本次是4。 第二步:左边(用i表示)从第二个数开始与基数进行比较(遇见比基数大的停止比较),右边(用j表示)从最右边开始与基数进行比较(遇见比基数小的停止比较) 第三步:当i,j停止时,它们所对应的值进行交换,直到i,j同时指向同一个值的时候,将这个值与基数进行交换。 接着进行循环这三个步骤,每一次基数的左边进行上面的操作,每一次基数的右边也进行上面的操作。直至排序完成。
这里先创建全局变量,为了减少内存的利用
cpp#include <stdio.h>
int arr[100], n;
int main()
{
return 0;
}
cppint a;
scanf("%d", &n);
for (a = 0; a < n; a++)
{
scanf("%d", &arr[a]);
}
cppwhile (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
cppwhile (i < j)
{
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;
3. 用递归的方式不断的进行排序,基数左边,右边都需要用递归,递归结束的条件(左下标大于右下标
cppif (i > j)
return 0;
quicksort(left, i);//左
quicksort(j+1, right);//右
该排序函数模块
cppint quicksort(int left,int right)
{
int temp = left;
int i = left;
int j = right - 1;
int t = 0;
if (i > j)
return 0;
while (i < j)
{
//下面比较一定要写等于,因为是从基数开始的必须要跳过基数
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;
quicksort(left, i);//左
quicksort(j+1, right);//右
return 0;
}
cppfor (a = 0; a < n; a++)
{
printf("%d ", arr[a]);
}
printf("\n");
听我讲了这么久,我们已经实现了快速排序 下面看完整的代码
cpp#include <stdio.h>
int arr[100], n;
int quicksort(int left,int right)
{
int temp = left;
int i = left;
int j = right - 1;
int t = 0;
if (i > j)
return 0;
while (i < j)
{
while (arr[j] >= arr[temp]&&i<j)
{
j--;
}
while (arr[i] <= arr[temp] && i < j)
{
i++;
}
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
t = arr[left];
arr[left] = arr[i];
arr[i] = t;
quicksort(left, i);//左
quicksort(j+1, right);//右
return 0;
}
int main()
{
int left, right;
int a;
scanf("%d", &n);
for (a = 0; a < n; a++)
{
scanf("%d", &arr[a]);
}
left = 0;
right = n;
quicksort(left,right);
for (a = 0; a < n; a++)
{
printf("%d ", arr[a]);
}
printf("\n");
return 0;
}