快速排序
第一种
#include <stdio.h>
int a[101], n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right)
{
int i, j, t, temp;
if (left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while (i != j)
{
//顺序很重要，要先从右边开始找
while (a[j] >= temp && i < j)
j--;
//再找右边的
while (a[i] <= temp && i < j)
i++;
//交换两个数在数组中的位置
if (i < j)
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort(left, i - 1);//继续处理左边的，这里是一个递归的过程
quicksort(i + 1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{
int i, j, t;
//读入数据
scanf_s("%d", &n);
for (i = 1; i <= n; i++)
scanf_s("%d", &a[i]);
quicksort(1, n); //快速排序调用
//输出排序后的结果
for (i = 1; i <= n; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
第二种
#include<iostream>
using namespace std;
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while (1) {
while (i < r && a[++i] < x);//注意i<r防止无限循环
while (a[--j] > x);
if (i >= j) break;//
swap(a, i, j);//注意两者顺序
}
//解答
swap(a, p, j);
return j;
}
void quicksort(int a[], int p, int r)
{
if (p < r) { //注意p<r为判断条件
int q = partition(a, p, r);
quicksort(a, p, q - 1);
quicksort(a, q + 1, r);
}
}
int main()
{
int i, a[100];
cout << "请输入元素个数：";
cin >> i;
cout << "请输入元素：" << endl;
for (int k = 0; k < i; k++)
{
cin >> a[k];
}
quicksort(a, 0, i - 1);
for (int k = 0; k < i; k++)
{
cout << a[k];
}
return 0;
}
