快捷導航

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

更新時間：2022年02月07日 17:12:12 作者：學好c語言的小王同學?

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

快速排序法：

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

示意圖：

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

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

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

直到排完

代碼實現(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 ;//給定下標
? ? ? ? int r=right;//給定下標
? ? ? ? int temp; //定義一個變量 作為中間值 交換 左右兩邊的元素位置
? ? ? ? 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){ //要讓左邊元素 往左邊移 右邊元素往右邊移 錯開
? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? ? ? r--;
? ? ? ? ? ? } //對左邊進行遞歸
? ? ? ? ? ? if(left<r){
? ? ? ? ? ? ? ? sort(arrays,left,r);
? ? ? ? ? ? }//對右邊進行遞歸
? ? ? ? ? ? if(right>l){
? ? ? ? ? ? ? ? sort(arrays,l,right);
?
? ? ? ? ? ? }
? ? ? ? }
? ? }
}

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

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

您可能感興趣的文章: