本文目錄一覽：
用JAVA實現快速排序算法？
本人特地給你編的代碼
親測
public class QuickSort {
public static int Partition(int a[],int p,int r){
int x=a[r-1];
int i=p-1;
int temp;
for(int j=p;j=r-1;j++){
if(a[j-1]=x){
// swap(a[j-1],a[i-1]);
i++;
temp=a[j-1];
a[j-1]=a[i-1];
a[i-1]=temp;
}
}
//swap(a[r-1,a[i+1-1]);
temp=a[r-1];
a[r-1]=a[i+1-1];
a[i+1-1]=temp;
return i+1;
}
public static void QuickSort(int a[],int p,int r){
if(pr){
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
public static void main(String[] stra){
int a[]={23,53,77,36,84,76,93,13,45,23};
QuickSort(a,1,10);
for (int i=1;i=10;i++)
System.out.println(a[i-1]);
}
}
那位大大能詳細的講解一下JAVA中的快速排序
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。最壞情況的時間複雜度為O(n2)，最好情況時間複雜度為O(nlog2n)。
另外 java沒指針概念 可以認為是句柄
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一趟快速排序的算法是：
1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N；
2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；
4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；
5）、重複第3、4步，直到I=J；
例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找X的值，6549,兩者交換，此時I：=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執行算法的第三步從後開始找)
進行第四次交換後： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大於X的值，9749,兩者交換，此時J：=4 )
此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那麼經過一躺快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {13} 27 {38}
結束 結束 {49 65} 76 {97}
49 {65} 結束
結束//下面是一個示例,哪位給說說快速排序法的原理,下面的示例中指針和上下標移動我看不太懂,
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
//聲明數組
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
//應用快速排序方法
quickSort(nums, 0, nums.length-1);
//顯示排序後的數組
for(int i = 0; i nums.length; ++i) {
System.out.print(nums[i] + “,”);
}
System.out.println(“”);
}
/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo = hi)
return;
//確定指針方向的邏輯變量
boolean transfer=true;
while (lo != hi) {
if (a[lo] a[hi]) {
//交換數字
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
//決定下標移動，還是上標移動
transfer = (transfer == true) ? false : true;
}
//將指針向前或者向後移動
if(transfer)
hi–;
else
lo++;
//顯示每一次指針移動的數組數字的變化
/*for(int i = 0; i a.length; ++i) {
System.out.print(a[i] + “,”);
}
System.out.print(” (lo,hi) = ” + “(” + lo + “,” + hi + “)”);
System.out.println(“”);*/
}
//將數組分開兩半，確定每個數字的正確位置
lo–;
hi++;
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
}
java如何實現鏈表
鏈表是一種重要的數據結構，在程序設計中佔有很重要的地位。C語言和C＋＋語言中是用指針來實現鏈表結構的，由於Java語言不提供指針，所以有人認為在Java語言中不能實現鏈表，其實不然，Java語言比C和C＋＋更容易實現鏈表結構。Java語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義，而非語言提供的數據類型），所以我們可以編寫這樣的類來實現鏈表中的結點。
class Node
{
Object data;
Node next;//指向下一個結點
}
將數據域定義成Object類是因為Object類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭，表頭必須包含指向第一個結點的指針和指向當前結點的指針。為了便於在鏈表尾部增加結點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表的大小，當調用者想得到鏈表的大小時，不必遍歷整個鏈表。下圖是這種鏈表的示意圖：
鏈表的數據結構
我們可以用類List來實現鏈表結構，用變量Head、Tail、Length、Pointer來實現表頭。存儲當前結點的指針時有一定的技巧，Pointer並非存儲指向當前結點的指針，而是存儲指向它的前趨結點的指針,當其值為null時表示當前結點是第一個結點。那麼為什麼要這樣做呢？這是因為當刪除當前結點後仍需保證剩下的結點構成鏈表，如果Pointer指向當前結點，則會給操作帶來很大困難。那麼如何得到當前結點呢，我們定義了一個方法cursor(),返回值是指向當前結點的指針。類List還定義了一些方法來實現對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進行各種操作。例如reset()方法使第一個結點成為當前結點。insert(Object d)方法在當前結點前插入一個結點，並使其成為當前結點。remove()方法刪除當前結點同時返回其內容，並使其後繼結點成為當前結點，如果刪除的是最後一個結點，則第一個結點變為當前結點。
鏈表類List的源代碼如下：
import java.io.*;
public class List
{
/*用變量來實現表頭*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整個鏈表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*鏈表複位，使第一個結點成為當前結點*/
{
Pointer=null;
}
public boolean isEmpty()
/*判斷鏈表是否為空*/
{
return(Length==0);
}
public boolean isEnd()
/*判斷當前結點是否為最後一個結點*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回當前結點的下一個結點的值，並使其成為當前結點*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回當前結點的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在當前結點前插入一個結點，並使其成為當前結點*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length＋＋;
}
public int size()
/*返回鏈表的大小*/
{
return (Length);
}
public Object remove()
/*將當前結點移出鏈表，下一個結點成為當前結點，如果移出的結點是最後一個結點，則第一個結點成為當前結點*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length－－;
}
return temp;
}
private Node cursor()
/*返回當前結點的指針*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*鏈表的簡單應用舉例*/
{
List a=new List ();
for(int i=1;i=10;i＋＋)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println(“There is no Node in List \n”);
System.in.println(“You can press return to quit\n”);
try
{
System.in.read();
//確保用戶看清程序運行結果
}
catch(IOException e)
{}
}
}
class Node
/*構成鏈表的結點定義*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
讀者還可以根據實際需要定義新的方法來對鏈表進行操作。雙向鏈表可以用類似的方法實現只是結點的類增加了一個指向前趨結點的指針。
可以用這樣的代碼來實現：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
當然，雙向鏈表基本操作的實現略有不同。鏈表和雙向鏈表的實現方法，也可以用在堆棧和隊列的實現中，這裡就不再多寫了，有興趣的讀者可以將List類的代碼稍加改動即可。
希望對你有幫助。
java 單鏈表排序問題
你的這個類，按照你的意思，應該有處理鏈表的方法。
比如有class A{
//there are many methods which you use them to do different jobs.
LinkList sort(LinkList p)
{
//處理鏈表排序
//返回鏈表
}
}
在你的主函數中，new 一個A，用A的對象調用A中那個排序的方法。作為一個方法寫在一個類中，提高了代碼的復用性。如果寫在主函數中，首先，看起來，很不爽，其次，如果你的程序中需要多次調用，你就沒啥子辦法。JAVA中不能使用GOTO語句。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/242455.html
微信掃一掃 
支付寶掃一掃 