当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

快速排序思想及其算法实现

发表于: 2013-10-23   作者:come_for_dream   来源:转载   浏览:
摘要:                            快速排序思想及其算法实现     快速排序(Quicksor

                           快速排序思想及其算法实现

 

 

快速排序(Quicksort)是对冒泡排序的一种改进。O(N*logN)的算法复杂度使它得到了广泛的应用。

算法的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中的一部分的所有数据都比另一部分都要小,然后按此方法分别对这两部分再分别进行快速排序,这呢哥哥排序过程可以递归处理。

<!--EndFragment-->

以此达到整个数据变成有序序列。

 

算法的过程为:

1.制定杻轴(一般是第一个元素)

2.通过一趟排序将一杻轴为中心,把待排记录分割成独立的两部分,使得左边的记录的关键字小于杻轴值,右边的记录大于杻轴值

3.对左右两部分记录序列重复上述过程,以此类推,直到子序列中只剩下一个记录或不含记录为止

 

 

对于

数据:25   21   65   2   35   7   5   43  

 

第一趟排序的结果:5   21   7   2   25     35   65   43  

第二趟排序的结果:  5   7   21   25   35   65   43 

第三趟排序的结果:2   5   7   21   25   35   65   43 

第四趟排序的结果:2   5   7   21   25   35   65   4

第五趟排序的结果:2   5   7   21   25   35   43   65

第六趟排序的结果:2   5   7   21   25   35   43   65

 

 

 

代码:

/**
	 * 快速排序
	 * 
	 * @param args
	 */

	public void quickSort(int a[], int left, int right) {
		int q;
		if (left < right) {

			q = partition(a, left, right);
			quickSort(a, left, q - 1);
			quickSort(a, q + 1, right);
			
			
		}

	}

	private int partition(int[] a, int left, int right) {
		int s;

		s = a[left];
	
		while (left <right){

			//向左判断
			while (a[right] > s) {
				right--;
			}
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				left++;
			}
			
			//向右判断
			while (a[left] < s) {
				left++;
			}
			//交换
			if(left<right){
				int temp = a[left];				
				a[left] = a[right];
				a[right] = temp;
				right--;
			}			
			 
		
		}
		//打印数组
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "   ");		
		}
		System.out.println();


		return left;
	}

 

快速排序思想及其算法实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号