如何使用java實(shí)現(xiàn)快速排序

這篇文章將為大家詳細(xì)講解有關(guān)如何使用java實(shí)現(xiàn)快速排序，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

1) 快速排序算法介紹

    快速排序(quicksort)是對(duì)冒泡排序的一種改進(jìn)。基本思想是:通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按照此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

2) 快速排序法示意圖:

3) 快速排序算法應(yīng)用實(shí)列:

    要求: 對(duì)[-9,78,0,23,-567,70] 進(jìn)行從小到大的排序,要求使用快速排序法。

    a. 如果取消左右遞歸,結(jié)果是 -9 -567 0 23 78 70

    b. 如果取消左右遞歸,結(jié)果是 -567 -9 0 23 78 70

    c. 如果取消左遞歸,結(jié)果是 -9 -567 0 23 70 78

    d. 代碼實(shí)現(xiàn)

import java.util.Arrays;

//快速排序
public class QuickSort {

	public static void main(String[] args) {
		int[] arr= {-9,78,0,23,-567,70, -1,900, 4561};
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		QuickSort.quickSort(arr, 0, arr.length-1);
		System.out.println("排序后");
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr,int left,int right) {
		int l = left;//左下標(biāo)
		int r = right;//右下標(biāo)
		//中軸值,中間值
		int pivot = arr[(left+right)/2];
		int temp = 0;//中間值,作為交換時(shí)使用
		/*while循環(huán)的目的是讓比pivot值小放到左邊,比pivot值大放到右邊
		 */
		while(l < r) {
			//在pivot的左邊一直找,找到大于等于pivot值,才退出
			while(arr[l]<pivot) {
				l+=1;
			}
			//在pivot的右邊一直找,找到小于等于pivot值,才退出
			while(arr[r]>pivot) {
				r-=1;
			}
			/*
			 * 如果l>=r說明pivot的左右兩的值,已經(jīng)按照左邊全部是小于等于pivot值,右邊全部是大于等于pivot
			 */
			if(l>=r) {
				break;
			}
			//交換
			temp=arr[l];
			arr[l]=arr[r];
			arr[r]=temp;
			//如果交換完后,發(fā)現(xiàn)這個(gè)arr[l]==pivot值 相等r--,前移
			if(arr[l]==pivot) {
				r-=1;
			}
			//如果交換完后,發(fā)現(xiàn)這個(gè)arr[r]==pivot值 相等l++,后移
			if(arr[l]==pivot) {
				l+=1;
			}
		}
		//如果l==r,必須l++,r--,否則會(huì)出現(xiàn)棧溢出
		if(l==r) {
			l+=1;
			r-=1;
		}
		//向左遞歸
		if(left<r) {
			quickSort(arr, left, r);
		}
		//向右遞歸
		if(right>l) {
			quickSort(arr, l, right);
		}
	}
}

關(guān)于“如何使用java實(shí)現(xiàn)快速排序”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。