`
韩悠悠
  • 浏览: 846553 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

快速排序

 
阅读更多

 * 快速排序
 * 一、快速排序的思想
 * 快速排序通过将一个数组划分成俩个子数组,然后通过递归调用自身为每一个子数组进行快速排序来实现
 * 二、如何进行划分
 * 设定关键字,将比关键字小的放在一组,比关键字大的放在另一组
 * 三、如何自动设定关键字
 * 设置数组最右端的数据为关键字

 

package com.algorithm;

/**
 * 快速排序
 * 一、快速排序的思想
 * 快速排序通过将一个数组划分成俩个子数组,然后通过递归调用自身为每一个子数组进行快速排序来实现
 * 二、如何进行划分
 * 设定关键字,将比关键字小的放在一组,比关键字大的放在另一组
 * 三、如何自动设定关键字
 * 设置数组最右端的数据为关键字
 * @author lenovo
 *
 */
public class QuickSort {

	/**
	 * 划分数组
	 */
	public static int partition(long attr[],int left,int right,long point){
		int leftPtr= left-1;
		int rightPrt = right +1;
		while (true) {
			//循环,比关键字小的留在左端
			while (leftPtr < rightPrt &&  attr[++leftPtr]<point) ;
			//将比关键字大的留在右边,
			while (rightPrt > leftPtr &&  attr[--rightPrt]>point) ;
			if(leftPtr >= rightPrt){
				break;
			}else{
				long temp = attr[leftPtr];
				attr[leftPtr] = attr[rightPrt];
				attr[rightPrt] =temp;
			}
		}
		
		//将关键字和当前leftPtr所指的这一个进行交换
		long tmp = attr[leftPtr];
		attr[leftPtr] =  attr[right];
		attr[right] = tmp;
		return leftPtr;
	}
	
	public static void sort(long[] arr, int left, int right) {
		if(right - left <= 0) {
			return;
		} else {
			//设置关键字
			long point = arr[right];
			//获得切入点,同时对数组进行划分
			int partition = partition(arr, left, right, point);
			//对左边的子数组进行快速排序
			sort(arr,left,partition - 1);
			//对右边的子数组进行快速排序
			sort(arr,partition + 1, right);
		}
	}
	
	public static void displayArr(long attr[]){
		System.out.print("[");
		for(long num : attr) {
			System.out.print(num + " ");
		}
		System.out.print("]");
		System.out.println();
	}
	
	public static void main(String[] args) {
		long[] attr = new long[10];
		
		for (int i = 0; i < 10; i++) {
			attr[i] = (long) (Math.random()*99);
		}
		displayArr(attr);
		
		sort(attr, 0, attr.length - 1);
		displayArr(attr);
	}
}

 

 

分享到:
评论

相关推荐

    快速排序 快速排序例子

    ### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...

    C语言实现多种链表快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...

    快速排序 快速排序快速排序快速排序

    快速排序快速排序 快速排序 快速排序 快速排序 快速排序

    确定性快速排序与随机化快速排序的比较

    快速排序是一种高效的排序算法,在计算机科学和数学中被广泛研究。其基本原理是分治法策略,即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn),但在最坏的情况下,它的时间复杂度可...

    简单的快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),即把一个大问题分解成若干个小问题来解决,最终将小问题的结果合并得到原问题的解。在这...

    排序算法编程 堆排序 快速排序

    本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...

Global site tag (gtag.js) - Google Analytics