快排思路
这里采用传统的方法,没有采用剑指Offer书上的方法。
Java版的比较干净,舍去了不必要的判断和操作,以Java版为准。
- 排序函数(全部采用闭区间):
当区间为null或者左指针>=右指针位置 return;//
partition 当前区间,得到随机枢轴元素的idx。
对idx分成的左右区间排序。 - partition函数
在当前区间,(随机选取一个元素和第一个元素置换),选第一个元素作为枢轴元素,确定它的位置(比它小于等于的放左边,比它大于等于的放右边)
具体的,采用“东拆西补”的思想,while(i!=j){
从右遍历找到比枢轴元素小的元素,放到i指向的位置,空出j位置;
从左遍历找到比枢轴元素大的位置,放到j指向的位置,空出i位置;
}
arr[i]=枢轴元素
return i
其他知识点
生成一个范围内随机数
见代码,这里为包含左右两端点。
srand((unsigned)time(0))
用来随机生成随机数种子。rand()
生成随机数。
数组做形参
数组具有不能传值的特性,当把数组作为形参,实际是把指向数组首元素的地址作为参数传递。
int partition(int *num,int start,int end)
int partition(int num[],int start,int end)
待解决
异常的解决还需要改,
现在遇到异常会输出:terminating with uncaught exception of type char const*
代码(Java)
public class QuikSort {
public static void main(String[] args) {
int[] arr= {4,5,7,2,2,3};
quickSort(arr,0,arr.length-1);
for(int num:arr) {
System.out.println(num);
}
}
public static void quickSort(int[] arr,int low,int high) {
if(arr==null||low>=high) {//
return;
}
int idx=partition(arr,low,high);
quickSort(arr,low,idx-1);
quickSort(arr,idx+1,high);
}
public static int partition(int[] arr,int low,int high) {
int key=arr[low];
int i=low;
int j=high;
while(i<j) {
while(i<j&&arr[j]>=key) {//
--j;
}
arr[i]=arr[j];//包含i、j相等情况
while(i<j&&arr[i]<=key) {
++i;
}
arr[j]=arr[i];
}
arr[i]=key;
return i;
}
}
代码(C++)
#include <iostream>
#include <time.h>
using namespace std;
int randomInRange(int start,int end){
if(end<start){
throw "Invaild paramters of randomInRange";
}
else{
srand((unsigned)time(0));
return start+rand()%(end-start+1);//对数据个数求余
}
}
void swap(int &a,int &b){//注意
int temp=a;
a=b;
b=temp;
}
int partition(int *num,int start,int end){
if(num==nullptr||start<0||(end-start)<0){//注意end-start=0可以;书上partition加了数组长度的形参
throw "Invaild paramters of partition";//,并要限制数组的长度大于0以及end在范围内,这里未做。
}
int index=randomInRange(start, end);
swap(num[index], num[start]);
int tempElm=num[start];
int i=start;
int j=end;
while(i<j){
while(i<j&&num[j]>=tempElm){//注意>=,因为等于基准元素的元素分在它的左右两边都可以
--j;
}
if(i!=j){
num[i]=num[j];
++i;
}
while(i<j&&num[i]<=tempElm){//注意>=
++i;
}
if(i!=j){
num[j]=num[i];
--j;
}
}
num[i]=tempElm;//最后一定是I j 都指向[]的位置
return i;
}
void quickSort(int *num,int start,int end){
if(start==end){return;}
int index=partition(num, start, end);
if(index>start){//注意
partition(num, start, index-1);
}
if(index<end){//注意
partition(num, index+1, end);
}
}
int main(int argc, const char * argv[]) {
int num[]={3,4,5,1,1,2};
int len=sizeof(num)/sizeof(int);
quickSort(num, 0, len-1);
for(int i=0;i<len;i++){
cout<<num[i]<<" "<<endl;
}
return 0;
}
reference
https://www.zybuluo.com/Ggmatch/note/1036346
https://blog.csdn.net/yuhan_9204/article/details/46427533