首页 > 代码库 > 快速排序
快速排序
原理:
基本思想:
1.从待排序列中任选一个元素作为轴点;
2.将序列中比轴点的值小的放到轴点左边,比轴点的值大的放到轴点右边;
3.以轴为分界线,分别对轴左边和右边部分递归进行1、2操作。
平均时间复杂度
尽管快速排序的最坏时间为O(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
空间复杂度
快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(lgn),故递归后需栈空间为O(lgn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。
尽管快速排序的最坏时间为O(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
空间复杂度
快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(lgn),故递归后需栈空间为O(lgn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。
具体步骤:
考虑序列{49,38,65,97,76,13,27}
先整体执行一次快速排序:
原始序列:
取第一个元素的值作为轴点:
low指针与high指针初始时,分别指向arr[low]和arr[high],首先将轴点与high指针所指元素进行比较,若比轴点大,那么指针前移,否则将这个比轴点小的元素值复制到low指针指向的位置:
接着,将轴点与low指针所值元素进行比较,若比轴点小,那么low指针后移,否则将这个比轴点大的元素的值复制到
high所指向的位置。27比轴点49小,不用管,low指针后移,38比轴点49小,不用管,low指针继续后移。此时,low指针指向65,比轴点大,那么应该复制到high指针所指位置:
此时发现low指针与high指针没有相交,那么继续上面的操作:
65比49大,high指针前移,13比49小,那么进行一次复制:
接下来,把97复制到13的位置:
此时,high指针发现97>49,前移,76>49,前移,发现low和high重合,那么循环结束,此时将轴点的值放到这个位置。
现在可以看到,经过上面的若干步骤后,轴点左边元素均比轴点小,右边均比轴点大。紧接着,对左边和右边部分执行上面的步骤(递归),最终将形成有序序列。
int partition(int arr[],int low,int high) { int val = arr[low];//以arr[low]作为轴点,val记录轴点的值 while(low < high) { while(low<high && arr[high] >= val) { high--; } arr[low] = arr[high];//将轴点右侧比轴点小的放到轴左边,使轴点右侧均比轴点大 while(low < high && arr[low] <= val) { low++; } arr[high] = arr[low];//将轴点左侧比轴点大的放到轴右边,使轴点左侧均比轴点小 } arr[low] = val; return low;//返回轴点的位置 } void quick_sort(int arr[],int low,int high) { int index;//记录轴点的位置 if(low < high) { index = partition(arr,low,high);//先对数组整体做一次快排,使轴左侧均比轴小,轴右侧均比轴大 quick_sort(arr,low,index-1);//接着,递归对轴左边部分进行快排 quick_sort(arr,index+1,high);//递归对轴右边进行快排 } }
完整代码:
/* 快速排序 by Rowandjj 2014/7/22 */ #include<iostream> using namespace std; int partition(int arr[],int low,int high) { int val = arr[low];//以arr[low]作为轴点,val记录轴点的值 while(low < high) { while(low<high && arr[high] >= val) { high--; } arr[low] = arr[high];//将轴点右侧比轴点小的放到轴左边,使轴点右侧均比轴点大 while(low < high && arr[low] <= val) { low++; } arr[high] = arr[low];//将轴点左侧比轴点大的放到轴右边,使轴点左侧均比轴点小 } arr[low] = val; return low;//返回轴点的位置 } void quick_sort(int arr[],int low,int high) { int index;//记录轴点的位置 if(low < high) { index = partition(arr,low,high);//先对数组整体做一次快排,使轴左侧均比轴小,轴右侧均比轴大 quick_sort(arr,low,index-1);//接着,递归对轴左边部分进行快排 quick_sort(arr,index+1,high);//递归对轴右边进行快排 } } int main() { //int arr[] = {4,2,1,6,9,11,3,5,8,10}; //int arr[] = {1,3,5,7,9,11,13,15,17,19}; int arr[] = {19,17,15,13,11,9,7,5,3,1}; int len = 10,i; quick_sort(arr,0,len); for(i = 0; i < len; i++) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
测试:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。