排序算法之快速排序原理与实战

说道排序，我相信大家并不模式。在写程序的生涯中我们随处可见到排序的使用场景，例如数据库sql排序。排序的算法有很多种，同时java等语言也都提供了排序的接口，方便大家进行简单排序功能。关于排序算法有很多种，如快速排序、直接插入排序、希尔排序、简单选择排序、二元选择排序、冒泡排序等。这些排序我将写一系列的文章进行原理解析和实例演示。

快速排序的原理是：使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
快速排序分解图如下：

快速排序具体实例源码如下：

package com.xttblog.sort;

public class QuickSort {
	//快速排序
	private static void quickSort(int s[], int l, int r){
		if(l>=r)
			return;
	    //将中间的这个数和第一个数交换 参见注1
		int i = l, j = r, x = s[l];
		while (i < j){
			while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
				j--;  
			if(i < j) 
				s[i++] = s[j];
			
			while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
				i++;  
			if(i < j) 
				s[j--] = s[i];
		}
		s[i] = x;
		quickSort(s, l, i - 1); // 递归调用 
		quickSort(s, i + 1, r);
	}
	
	public static void main(String[] args) {
		int s [] = {67,23,89,35,28,90,10,24};
		for (int i : s) {
			System.out.print(i+" ");
		}
		quickSort(s,0,7);
		System.out.println();
		for (int i : s) {
			System.out.print(i+" ");
		}
		//排序前后输入结果为：
		//67 23 89 35 28 90 10 24 
		//10 23 24 28 35 67 89 90 
	}
}

版权声明：本文为博主原创文章，未经博主允许不得转载。原文地址http://www.xttblog.com/?p=433

： » 排序算法之快速排序原理与实战