快速排序

该段代码添加了随机选取主元功能，将随机选取的主元和最后一个位置的元素换一下，便于排序过程。通过i划分小于主元和大于主元的元素，j划分大于主元元素和未排序元素。每次while循环之后i落在第一个大于主元的元素上，j落在第一个未排序元素上。因此判断过程中，当j位置元素大于主元则，j自己向后加一个，i则不动发，如果j位置元素小于主元，因为i每次循环开始都位于大于主元元素的第一个位置上（小于主元的最后一个元素的下一个位置），因此交换i和j位置的元素即可，并将i和j都自增一个。完成后，将i位置元素和最后一个元素换一下，此时i位置前的元素都小于i位置元素，i位置后的元素都大于i位置元素。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>int MainElem(int p, int r, int* arr){if(p >= r) return p;srand(time(NULL));int q =  rand() % ( r - p + 1) + p;int item = arr[q];arr[q] = arr[r];arr[r] = item;int i,j;i = j = p;while(j < r){if(arr[j]<arr[r]){item = arr[i];arr[i] = arr[j];arr[j] = item;i++;j++;}else {j++;}}item = arr[i];arr[i] = arr[r];arr[r] = item;return i;
}void QuickSort(int p, int r, int* arr){if(p < r){int q = MainElem(p, r,arr);QuickSort(p, q-1, arr);QuickSort(q+1, r, arr);}}int main(){int a[10] = {0, 89, 78, 65, 89, 786, 78, 45, 8, 6};QuickSort(0, 9, a);for(int i = 0; i < 10; i ++){printf("%d\n", a[i]);}return 0;
}

后续

考虑了一下初始状态，i和j相等，相等的话当出现i位置元素小于r位置元素需要将i和j位置元素进行交换，此时i和j位置相同，原代码中没考虑这一点会导致“原地调整”，因此使用一个if语句规避原地调整。

int MainElem(int p, int r, int* arr){if(p >= r) return p;srand(time(NULL)); //设置种子int q =  rand() % ( r - p + 1) + p;int item = arr[q];arr[q] = arr[r];arr[r] = item;int i,j;i = p;j = p;while(j < r){if(arr[j]<arr[r]){if(j != i){ //增加了一个if语句item = arr[i];arr[i] = arr[j];arr[j] = item;}i++;j++;}else {j++;}}item = arr[i];arr[i] = arr[r];arr[r] = item;return i;
}