JAVA算法起步之快速排序?qū)嵗?/h1>

 更新時(shí)間：2014年02月10日 15:13:17   作者：  

這篇文章主要介紹了JAVA算法起步之快速排序?qū)嵗?需要的朋友可以參考下

快速排序一聽這個(gè)名字可能感覺很快，但是他的算法時(shí)間復(fù)雜度最壞情況卻跟插入排序是一樣的。之所以成為快速排序是因?yàn)樗钠骄时榷雅判蜻€要快，快速排序也是基于分治思想與歸并排序差不多，但是快速排序是原址的，直接在原數(shù)組操作不需要再開辟新的存儲(chǔ)空間?？焖倥判虻乃枷牒芎唵?，就是選定一個(gè)關(guān)鍵字k將原數(shù)組分成兩份g1與g2，g1中所有的元素都比k小或者相等，而g2中所有的數(shù)據(jù)都比k大或者等于，這樣對g1與g2分別進(jìn)行快速排序，最終我們得到的就是一個(gè)有序的數(shù)組。代碼中的sort方法就是對剛才語句的描述。而關(guān)鍵的算法就是去尋找k的位置將原數(shù)組分為大小兩部分的過程。方法getPlocation就是快速排序的核心。他的實(shí)現(xiàn)原理有點(diǎn)像插入排序只是有點(diǎn)像。每次都把map中end位置的元素作為關(guān)鍵字，通過與end元素對比將數(shù)組分成大小兩部分，而i與j則是兩個(gè)分割線，i與j之間的數(shù)都是比core大的元素，i與j就像一條貪吃蛇，當(dāng)j的下一個(gè)數(shù)比core大的時(shí)候j+1，i到j(luò)的長度增大了，而如果比core小的話，i與j都向前走一下，并將那個(gè)小數(shù)放在i的前面。這樣循環(huán)一遍后，start到end-1之間就是按大小分開的，最后將core放在中間，將core的位置返回就是分界線了。

復(fù)制代碼 代碼如下:

public class QuickSort {
 public int getPlocation(int[] map,int start,int end){
  int core=map[end];
  int i=start-1;
  for(int j=start;j<=end-1;j++){
   if(map[j]<=core){
    i++;
    int cache=map[j];
    map[j]=map[i];
    map[i]=cache;
   }
  }
  i++;
  map[end]=map[i];
  map[i]=core;
  return i;
 }
 public void sort(int[] map,int start,int end){
  if(start<end){
  int p=getPlocation(map, start, end);
  sort(map, start, p-1);
  sort(map,p+1,end);
  }
 }
 public static void main(String[] args) {
  int[] map=new int[]{4,1,5,3,7,12,65,7};
  QuickSort qs=new QuickSort();
  qs.sort(map, 0, map.length-1);
  for (int i = 0; i < map.length; i++) {
   System.out.println(map[i]);
  }
 }
}

您可能感興趣的文章:

• Java算法之?dāng)?shù)組冒泡排序代碼實(shí)例講解
• Java算法之串的簡單處理
• Java算法實(shí)現(xiàn)調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)之前的講解
• Java算法實(shí)現(xiàn)楊輝三角的講解
• Java算法之冒泡排序?qū)嵗a
• Java算法之最長公共子序列問題(LCS)實(shí)例分析
• java算法實(shí)現(xiàn)紅黑樹完整代碼示例
• Java算法之堆排序代碼示例
• java算法之二分查找法的實(shí)例詳解
• java算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼
• java算法實(shí)現(xiàn)預(yù)測雙色球中獎(jiǎng)號(hào)碼
• Java算法之遞歸算法計(jì)算階乘
• JAVA算法起步之插入排序?qū)嵗?/a>
• JAVA算法起步之堆排序?qū)嵗?/a>
• 關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
• Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算

• JAVA
• 快速排序

相關(guān)文章

• 

  在java中由類名和方法名字符串實(shí)現(xiàn)其調(diào)用方式

  這篇文章主要介紹了在java中由類名和方法名字符串實(shí)現(xiàn)其調(diào)用方式，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧

  2020-09-09
• 

  JAVA字符串占位符使用方法實(shí)例

  今天同事又問起類似符串占位符使用的功能,所以下面這篇文章主要給大家介紹了關(guān)于JAVA字符串占位符使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

  2022-11-11
• 

  Servlet實(shí)現(xiàn)簡單文件上傳功能

  這篇文章主要為大家詳細(xì)介紹了Servlet實(shí)現(xiàn)簡單文件上傳功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

  2017-10-10
• 

  Java中Klass模型與類加載的詳細(xì)機(jī)制

  這篇文章主要介紹了Java中Klass模型與類加載的詳細(xì)機(jī)制,java語言是在jvm中運(yùn)行而jvm是不認(rèn)識(shí)java代碼的我們使用javac編譯的class文件jvm是不認(rèn)識(shí)的 所以有一個(gè)類加載的動(dòng)作 這個(gè)動(dòng)作就是把class字節(jié)碼拼裝成一個(gè)klass類型,需要的朋友可以參考下

  2023-08-08
• 

  VsCode搭建Spring Boot項(xiàng)目并進(jìn)行創(chuàng)建、運(yùn)行、調(diào)試

  這篇文章主要介紹了VsCode搭建Spring Boot項(xiàng)目并進(jìn)行創(chuàng)建、運(yùn)行、調(diào)試 ，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

  2020-05-05
• 

  詳解怎么用Java的super關(guān)鍵字

  今天帶大家學(xué)習(xí)Java中super關(guān)鍵字是怎么用的,文中有非常詳細(xì)的介紹,對正在學(xué)習(xí)的小伙伴們很有幫助,需要的朋友可以參考下

  2021-06-06
• 

  java開發(fā)RocketMQ生產(chǎn)者高可用示例詳解

  這篇文章主要為大家介紹了java開發(fā)RocketMQ生產(chǎn)者高可用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

  2022-08-08
• 

  Java實(shí)現(xiàn)字符數(shù)組全排列的方法

  這篇文章主要介紹了Java實(shí)現(xiàn)字符數(shù)組全排列的方法,涉及Java針對字符數(shù)組的遍歷及排序算法的實(shí)現(xiàn)技巧,需要的朋友可以參考下

  2015-12-12
• 

  Java面向?qū)ο笾^承性的實(shí)例代碼詳解

  這篇文章主要介紹了Java面向?qū)ο笾^承性，文中代碼簡單易懂，可以更好的幫助大家學(xué)習(xí)，有興趣的小伙伴快來了解下

  2020-05-05
• 

  SpringBoot利用自定義注解實(shí)現(xiàn)隱私數(shù)據(jù)脫敏(加密顯示)的解決方案

  這兩天在整改等保測出的問題,里面有一個(gè)“用戶信息泄露”的風(fēng)險(xiǎn)項(xiàng)（就是后臺(tái)系統(tǒng)里用戶的一些隱私數(shù)據(jù)直接明文顯示了）,其實(shí)指的就是要做數(shù)據(jù)脫敏,本文給大家介紹了SpringBoot利用自定義注解實(shí)現(xiàn)隱私數(shù)據(jù)脫敏(加密顯示)的解決方案,需要的朋友可以參考下

  2023-11-11

最新評論