5快速排序-其它3

#include <iostream>
using namespace std;

/*  第一个为中心轴或pivot ,值取出存入第三变量中，从第1位置，和最后
位置，定义i和j 指针，先从j向前找比pivot小的位置，将此值放到i位置，i向前
移动找的第一个大于pivot的值，再将值移动到j位置，依次进行，当两个指针指向同
一位置，将pivot放置此处。完成一趟排序*/
int copy1 = 0;
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 << "---" << copy1 << endl;
}

void qsort(int l, int r) {
    copy1 = a[l];
    swapNumber++;
    a[l] = -1;
    showA();
    int i = l;
    int j = r;

    while (j > i) {
        while (j > i && a[j] >= copy1) {  // 右边找到小的
            j--;
            pmoves++;
        }
        if (i == j) {//两指针重叠时推出
            break;
        } else {//移动到左边空位
            a[i] = a[j];
            swapNumber++;
            a[j] = -1;
        }
        showA();

        while (i<j && a[i] < copy1) {  // 左边大的
            i++;
            pmoves++;
        }
        if (i == j) {//两指针重叠时推出
            break;
        }else{//移动到右边空位
            a[j] = a[i];
             swapNumber++;
            a[i] = -1;
        }
        showA();
    }
    a[j] = copy1;//复制的值放回空位；
    showA();
    if (j - l > 1)
        qsort(l, j - 1);  // 若未到两个数的边界，则递归搜索左右区间
    if (r - (j+1) > 1)
        qsort(j+1, r);
}

int main() {
    showA();
    qsort(0, len - 1);
    cout << " 交换次数:" << swapNumber << endl;
    cout << " 指针移动数:" << pmoves << endl;
}