
5快速排序-其它2
发布时间:
思想
第一个为中心轴 定义大于中心轴的两个指针范围 ij,发现小于轴心中的值与i位置交换i++,j++ 遍历完中心轴交换到相应位置。
js
#include <iostream>
using namespace std;
int a[] = {3, 1, 7, 4, 9, 6, 2, 5, 8};
int len = sizeof(a) / sizeof(a[0]);
int pmoves = 0;
int swapNumber = 0;
void showA() {
for (int i = 0; i < len; i++) {
cout << a[i] << " ";
}
cout << "---" << endl;
}
void qsort(int l, int r) {
int pivot = l; // 将当前序列在中间位置的数定义为分隔数
int j = l + 1;
int i;
while (a[j] < a[pivot]) {
j++;
}
i = j;
while (j < r) {
if (a[j + 1] < a[pivot]) { // 见到小的 换
swap(a[j + 1], a[i]);
showA();
j++;
i++;
} else {
j++;
}
};
if (i > pivot) { // 中轴数换到指定位置
swap(a[i - 1], a[pivot]);
}
showA();
if (i - l> 2)
qsort(l, i - 2 ); // 若未到两个数的边界,则递归搜索左右区间
if (r - i > 2)
qsort(i , r);
}
int main() {
qsort(0, len - 1);
cout << " 交换次数:" << swapNumber << endl;
cout << " 指针移动数:" << pmoves << endl;
}