2、定义一个begin和一个end#xff0c;begin从左向右走#xff0c;end从右向左走。

#xff08;需要注意的是#xff1a;若选择最左边的数据作为key#xff0c;则…

快速排序法

2、定义一个begin和一个endbegin从左向右走end从右向左走。

需要注意的是若选择最左边的数据作为key则需要end先走若选择最右边的数据作为key则需要bengin先走。

3、在走的过程中若end遇到小于key的数则停下begin开始走直到begin遇到一个大于key的数时将begin和right的内容交换end再次开始走如此进行下去直到begin和end最终相遇此时将相遇点的内容与key交换即可。

选取最左边的值作为key

4.此时key的左边都是小于key的数key的右边都是大于key的数

5.将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作此时此部分已有序

tip1

{srand((size_t)time(NULL));return

rand()

原因对于很小和部分有序的数组快排不如插排好。

当待排序序列的长度分割到一定大小后继续分割的效率比插入排序要差此时可以使用插排而不是快排

截止范围待排序序列长度N

10虽然在5~20之间任一截止范围都有可能产生类似的结果这种做法也避免了一些有害的退化情形。

(right

//三数取中Swap(arr[mid],arr[left]);

kevi

arr[kevi]){right--;}//left找大while

(left

arr[kevi]){left;}//交换(大和小的)Swap(arr[left],

arr[right]);}//交换key和相遇点Swap(arr[kevi],

arr[right]);kevi

选key左边为key(坑)右边先走找小小于key,找到把值放key坑里,此时right变新坑左边后走找大大于key,找到把值放key坑里,此时left变新坑。

一直相遇把一开始key的值放相遇点递归下去

2.图解

kevi){right--;}Swap(arr[right],

arr[keng]);

}//最终把kevi放keng位置(相遇点)arr[keng]

kevi;//递归QuickSort_keng(arr,begin,keng-1);QuickSort_keng(arr,

keng1,

1、选出一个key一般是最左边或是最右边的。

2、起始时prev指针指向序列开头cur指针指向prev1前后指针。

3、若cur指向的内容小于key则prev先向后移动一位然后交换prev和cur指针指向的内容然后cur指针4、若cur指向的内容大于key则cur指针直接。

如此进行下去直到cur到达end位置此时将key和prev指针指向的内容交换即可。

经过一次单趟排序最终也能使得key左边的数据全部都小于keykey右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时便停止操作

2.图解

cur){//把小的交换到前面Swap(arr[cur],arr[prev]);}cur;}//cur越界了交换kevi和prevSwap(arr[kevi],

arr[prev]);kevi

使用stack来存储待处理的区间先入栈的是右端点然后是左端点。

执行一趟快速排序的划分操作使用kevi作为基准元素的索引prev用于记录小于基准元素的最后一个元素的位置。

在while循环中cur遍历当前区间如果发现比基准元素小的元素则将其与prev位置的元素交换。

划分完成后将基准元素与prev位置的元素交换确保基准元素位于中间位置。

检查新的区间是否需要继续排序如果需要则将新的区间端点压入栈中。

2.图解

//栈//先入右后入左st.push(end);st.push(begin);//不为空while

left

arr[cur]);}cur;}//把kevi换到相遇点Swap(arr[kevi],arr[prev]);kevi

prev;//入栈新区间-先右后左//