经典排序算法—-快排

由于很久没有刷题,现在来复习一下快速排序算法。

首先观察一下此图。

经典排序算法—-快排插图

观察此图我们可以得出,快排是选择基准数 + 分治。

它的基本思想为:

1.先从数列中取出一个数作为基准数
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。

接下来我们以该数组为例子:

数组大小为:9

int a[] = {20,5,9,10,15,3,21,1,55,50};

我们先观察第一次分区。0 – 9的分区.l = 0 r = 9

  1. 取基准数temp = a[ l ];
    int a[] = {20,5,9,10,15,3,21,1,55,50};
  2. 从高位向低位查找比temp的数 while( temp<a[j] && j>i) j–;,找到后,数组变化。a[i++] = a[j] 条件i<j
    int a[] = {1,5,9,10,15,3,21,1,55,50};
  3. 从低位位向高位查找比temp的数while( temp>=a[i] && i<j) i++,找到后,数组变化。填入a[j–] = a[i] 条件要i<j
    {1,5,9,10,15,3,21,21,55,50}; 

此时i<j 已经不成立,不能再往下继续查找。此时将基准数还原到数组中s[i] = temp;或 s[j] = temp。查找的结束条件 i==j 了。另外:i + j = 9分区大小。

{1,5,9,10,15,3,20,21,55,50}; 

继续重复1 – 3步骤

while( temp<a[j] && j>i) j–; 解读,高位向低位查找,a[j]比temp大继续往前找,直到temp>a[j]。

贴源代码:

#include<bits/stdc++.h>
using namespace std;
/*
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。  */
int AdjustArray(int s[],int l, int r){
	if(l<r){
		int i = l,j=r;
		int temp = s[l];
		while(i<j){
			//从右向左找出比基准数小的数
			while(s[j]>temp && i<j) j--; 
			if(i<j){
				s[i++] = s[j];
			}
			//从左边向右查找比基准大的数 
			while(s[i]<=temp && j>i) i++;
			if(i<j){
				s[j--]=s[i];
			} 	
		}
		s[i] = temp;
		AdjustArray(s,l,i-1);
		AdjustArray(s,i+1,r);
	}
}
int main (){
	int a[] = {20,5,9,10,15,3,21,1,55,50};
	int n = 10;
	AdjustArray(a,0,9);
	for(int i=0;i<10;i++){
		printf("%d ",a[i]);
	}
	
	
} 

 

 

 

文章已创建 80

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部