快捷導(dǎo)航

java 數(shù)據(jù)結(jié)構(gòu)與算法 (快速排序法)

更新時(shí)間：2022年02月07日 17:12:12 作者：學(xué)好c語(yǔ)言的小王同學(xué)?

這篇文章主要介紹了java 數(shù)據(jù)結(jié)構(gòu)與算法(快速排序法),，快速排序法是實(shí)踐中的一種快速的排序算法，在c++或?qū)ava基本類(lèi)型的排序中特別有用,下面我們一起進(jìn)入文章學(xué)習(xí)更詳細(xì)的內(nèi)容吧,需要的朋友可以參考下

快速排序法：

顧名思議，快速排序法是實(shí)踐中的一種快速的排序算法，在c++或?qū)ava基本類(lèi)型的排序中特別有用。它的平均運(yùn)行時(shí)間是0（N log N）。該算法之所以特別快，主要是由于非常精練和高度優(yōu)化的內(nèi)部循環(huán)。
快速排序是對(duì)冒泡法的一種改進(jìn)。通過(guò)一趟排序?qū)⒁判虻牡臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分所有的數(shù)據(jù)要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

示意圖：

這里定義最左邊元素為left 最右邊元素為right

p 元素的值就是 2對(duì)應(yīng)的索引 0 加上 5對(duì)應(yīng)的索引 7 之和除以2 得到索引為3 對(duì)應(yīng)的元素7

用左邊大于 7的數(shù)跟右邊小于7的數(shù)進(jìn)行交換位置一直進(jìn)行并且中間的p也要一直變化位置

直到排完

代碼實(shí)現(xiàn)：

import java.util.Arrays;
?
public class kuaisu {
? ? public static void main(String[] args) {
? ? ? ? int arrays[]=new int[]{2,9,4,7,3,3,6,5};
? ? ? ? sort(arrays,0,arrays.length-1);
? ? ? ? System.out.println(Arrays.toString(arrays));
?
?
? ? }

? public ?static ?void ?sort(int arrays[],int left,int right){
? ? ? ? int l=left ;//給定下標(biāo)
? ? ? ? int r=right;//給定下標(biāo)
? ? ? ? int temp; //定義一個(gè)變量 作為中間值 交換 左右兩邊的元素位置
? ? ? ? int pivot=arrays[(left+right)/2];//中間值
? ? ? ? while(l<r){
? ? ? ? ? ? //在左邊查找小于中間值得元素
? ? ? ? ? ? while(arrays[l]<arrays[pivot]){
? ? ? ? ? ? ? ? l++;
?
? ? ? ? ? ? }
? ? ? ? ? ? //同理在右邊查找大于中間值得元素
? ? ? ? ? ? while(arrays[r]>arrays[pivot]){
? ? ? ? ? ? ? ? r--;
? ? ? ? ? ? }//直到左邊元素大于右邊元素就結(jié)束
? ? ? ? ? ? if(l>=r){
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? temp=arrays[l];
? ? ? ? ? ? arrays[l]=arrays[r];
? ? ? ? ? ? arrays[r]=temp;
? ? ? ? ? ? //交換完arrays[l]=pivot
? ? ? ? ? ? if(arrays[l]==pivot){
? ? ? ? ? ? ? ? r--;
? ? ? ? ? ? }
? ? ? ? ? ? if(arrays[r]==pivot){
? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? }
? ? ? ? ? ? if(r==l){ //要讓左邊元素 往左邊移 右邊元素往右邊移 錯(cuò)開(kāi)
? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? ? ? r--;
? ? ? ? ? ? } //對(duì)左邊進(jìn)行遞歸
? ? ? ? ? ? if(left<r){
? ? ? ? ? ? ? ? sort(arrays,left,r);
? ? ? ? ? ? }//對(duì)右邊進(jìn)行遞歸
? ? ? ? ? ? if(right>l){
? ? ? ? ? ? ? ? sort(arrays,l,right);
?
? ? ? ? ? ? }
? ? ? ? }
? ? }
}

控制臺(tái)輸出結(jié)果如下：

到此這篇關(guān)于java 數(shù)據(jù)結(jié)構(gòu)與算法 (快速排序法)的文章就介紹到這了,更多相關(guān)java 數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: