首页 > 其他 > 详细

排序算法之快速排序

时间:2014-05-22 06:48:14      阅读:266      评论:0      收藏:0      [点我收藏+]


这一个博客将快速排序讲的挺好的:http://blog.csdn.net/morewindows/article/details/6684558


一、算法思想描述

1)令i = L,j = R,将基准数挖出形成第一个坑(基准数可以选择第一个位置上的数作为基准数,也可以选择其他位置上的数作为基准数)。

2)j--   。从后往前扫,找到第一个比基准数小的数。并将其“挖出”,填到上一个形成的坑中arr[i]

3)i++ 。 从前往后扫,找到第一个比基准数大的数。并将其“挖出”,填到上一个形成的坑中arr[j]

4)不断地重复2)、3)直到i == j,将基准数天津最后一个坑中arr[i]


二、算法分析

bubuko.com,布布扣


三、算法实现

/*
 * quicksort.cpp
 *
 *  Created on: 2014年5月18日
 *      Author: pc
 */


#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 10;
int arr[maxn];


void quicksort(int arr[],int l,int r){
	int i = l;
	int j = r;
	int x = arr[l];//将最左边的数作为基准数

	if(l < r){
		while(i < j){//如果i!=j就不断的进行循环

			while(i < j && arr[j] >= x){//从后往前扫,找到第一个比基准数小的数
				--j;
			}
			if(i < j){//如果找到了
				arr[i++] = arr[j];//将坑填上,并将i的值++
			}

			while(i < j && arr[i] <= x){//从前往后扫,找到第一个比基准数大的数
				++i;
			}
			if(i < j){
				arr[j--] = arr[i];//将坑填上,并将j的值--
			}
		}
		arr[i] = x;//将最后的基准位置上的坑填上

		//分治策略
		quicksort(arr,l,i-1);//递归调用
		quicksort(arr,i+1,r);
	}
}


void createReverseArr(){
	int i = 0;
	for(i = 0 ; i < maxn ; ++i){
		arr[i] = maxn - i;
	}
}

void printArr(){
	int i;
	for(i = 0 ; i < maxn ; ++i){
		printf("%d " , arr[i]);
	}
	printf("\n");
}

int main(){
	createReverseArr();
	printArr();
	quicksort(arr,0,maxn-1);
	printArr();
}





排序算法之快速排序,布布扣,bubuko.com

排序算法之快速排序

原文:http://blog.csdn.net/hjd_love_zzt/article/details/26160267

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!