快色排序算法(C语言描述)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

快速排序

算法思想

快速排序采用了一种分治策略，学术上称之为分治法（Divide-and-Conquer Method）。

哨兵（如下算法中的key）

每趟排序将哨兵插入到数组的合适位置，使得哨兵左侧的所有元素比哨兵大，右侧所有元素比哨兵小。

然后，哨兵左侧数组继续此操作（递归调用），哨兵右侧数组亦然，迭代此过程，最终使得数组有序。

快速排序算法（c语言描述）

void sort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left]; while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
} a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/ while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
} a[j] = a[i];
} a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - );/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + , right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}