2021.10.12

2021.10.12

快速排序 

双指针法，递归，选择哨兵 

int sort(int* data, int left, int right) {//每一次递归，每调用一次，确定一个值的正确位置if (left >= right)return 0;int i = left;int j = right;int key = data[left];while (i < j) {//并不是多余的，此可确定哨兵的位置while (i < j && key < data[j]) {//当哨兵值小于data[j]时，j前移j--;}data[i] = data[j];//哨兵值大于data[j]时,交换ij的值while (i < j && key >= data[i]) { i++;//当哨兵值大于data[i]时，i后移}data[j] = data[i];//哨兵值小于data[i]时，交换ij的值}data[i] = key;//i == j 时，将哨兵值赋值给i//递归排序sort(data, left, i - 1);sort(data, i + 1, right);
}int quick_sort(int* data, int length) {sort(data, 0, length - 1);
}