史上最详尽的快速排序描述【图】

快速排序的核心是要有一个基准数据temp，一般取数组的第一个位置元素。然后需要有两个指针left和right，分别指向数组的第一个和最后一个元素。

首先从right开始，比较right位置元素和基准数据。如果大于等于，则将right指针左移，比较下一位元素；如果小于，就将right指针处数据赋给left指针处（此时left指针处数据已保存进temp中），left指针+1，之后开始比较left指针处数据。

拿left位置元素和基准数据进行比较。如果小于等于，则将left指针右移，比较下一位元素；而如果大于就将left指针处数据赋给right指针处，right指针-1，之后开始比较right指针处数据…重复这个过程。

直到left和right指针相等时，说明这一次比较过程完成。此时将先前存放进temp中的基准数据赋值给当前left和right指针共同指向的位置处，即可完成这一次排序操作。

之后递归排序基础数据的左半部分和右半部分，递归的过程和上面讲述的过程是一样的，只不过数组范围不再是原来的全部数组了，而是现在的左半部分或右半部分。当全部的递归过程结束后，最终结果即为排好序的结果。

快速排序执行示意图：

/** 快速排序** 参数说明：*     a -- 待排序的数组*     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)*     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)*/
void quick_sort(int a[], int l, int r)
{if (l < r){int i,j,x;i = l;j = r;x = a[i];while (i < j){while(i < j && a[j] > x)j--; // 从右向左找第一个小于x的数if(i < j)a[i++] = a[j];while(i < j && a[i] < x)i++; // 从左向右找第一个大于x的数if(i < j)a[j--] = a[i];}a[i] = x;quick_sort(a, l, i-1); /* 递归调用，排序锚点左边部分 */quick_sort(a, i+1, r); /* 递归调用，排序锚点右边部分*/}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！