200字范文 > 很容易理解的C语言快速排序算法(完整注释+完整输出)

很容易理解的C语言快速排序算法(完整注释+完整输出)

时间：2019-08-07 21:37:34

#include <stdio.h>void quickSort(int arr[], int low, int high)//arr是传进来的数组,low和high是两个指针的预定值{int k;int head = low;//头针值int tail = high;//尾针值int PivotKey = arr[head];//设定标定为头指针if(low >= high)return;printf("本次循环开始前,Head/tail/PivotKey(arr_head)的值分别为%d,%d,%d.循环开始.\n",head,tail,PivotKey);while(head < tail)//当头指针小于尾指针(正常情况下){//反向扫描,后往前扫描一次,如果是正序则尾指针-1,这是个循环.直到不满足才执行arr[head] = arr[tail];while(head < tail && arr[tail] > PivotKey)//这里有一个点就是条件是"与",即此时比较的可以是head,也可以是arr[tail],{printf("改变前的tail指针位置为:%d,\n",tail);tail--;printf("改变后的tail指针位置为:%d,\n",tail);}arr[head] = arr[tail];//将tail的值向前交换,但是tile本身不动.此时arr[head]的值还在PivotKey中printf("第一个循环将tail值(%d)给了head,此时的数组为:",tail);for(k = 0; k < 5; k++) printf("%d ", arr[k]); printf("\n");printf("此时的PivotKey(arr_head)的值为%d.反向循环执行完.\n",PivotKey);//正向扫描,前往后扫描一次,如果是正序则头指针+1,这是个循环.直到不满足才执行arr[tail] = arr[head];while(head < tail && arr[head] < PivotKey)这里有一个点就是条件是"与",即此时比较的可以是head,也可以是arr[head],因为arr[head]还是没有被替换的原来的值,所以比较依然可以成功{printf("改变前的head指针位置为%d,\n",head);head++;printf("改变后的head指针位置为%d,\n",head);}arr[tail] = arr[head];//此时while条件不满足了,说明反序了,执行交换,此时PivotKey中的值被赋给后面的tail.printf("第二个循环将head值(%d)给了tail.此时的数组为:",head);for(k = 0; k < 5; k++) printf("%d ", arr[k]); printf("\n");printf("此时的PivotKey(arr_head)的值为%d.正向循环执行完.\n",PivotKey);printf("本次循环结束时,Head/tail/PivotKey(arr_head)的值分别为%d,%d,%d.\n",head,tail,PivotKey);}//此时head<tail条件不满足,退出一次循环arr[head] = PivotKey;printf("本次排序结束,此时PivotKey被重新赋值为:%d\n",PivotKey);for(k = 0; k < 5; k++)printf("%d ", arr[k]);printf("\n");printf("\n");quickSort(arr, low, head-1);//继续排序算法,此算法结束后左区间有序quickSort(arr, head+1, high);//继续排序算法,此算法结束后又区间有序,整个算法完成.(这两个递归如果条件满足会被持续调用)}int main(){int i;int a[5] = {2, 0, 9,1,8};for(i = 0; i < 5; i++)printf("%d ", a[i]);printf("\n");quickSort(a, 0, 4);for(i = 0; i < 5; i++)printf("%d ", a[i]);printf("\n");return 0;}

输出结果为:

2 0 9 1 8

本次循环开始前,Head/tail/PivotKey(arr_head)的值分别为0,4,2.循环开始.

改变前的tail指针位置为:4,

改变后的tail指针位置为:3,

第一个循环将tail值(3)给了head,此时的数组为:1 0 9 1 8

此时的PivotKey(arr_head)的值为2.反向循环执行完.

改变前的head指针位置为0,

改变后的head指针位置为1,

改变前的head指针位置为1,

改变后的head指针位置为2,

第二个循环将head值(2)给了tail.此时的数组为:1 0 9 9 8