交換排序是另一種經常使用的內部排序策略，常見的算法有冒泡排序和快速排序，之所以把冒泡排序和快速排序歸類為交換排序，是因為這兩種算法的主要工作是不斷的交換元素來達到排序的目的。

冒泡排序是最經典的交換排序，它的算法思想是：(假設數據存放在數組a[n]中)

1.比較a[0]和a[1]，如果a[0]>a[1]，則交換a[0]，a[1]，然后比較新的a[1](可能是原來的a[0])和a[2]，如果a[1]>a[2]，則交換　　　　a[1]，a[2]，以此類推，直到a[n-2]和a[n-1]比較完畢，這樣，a中的最大數就“沉底”了，即a[n-1]是數組a中的最大值。

2.從頭開始繼續第1步的操作，所不同的是本次比較到a[n-2]即可結束，這樣數組a中的次大值就被交換到a[n-2]的位置。

3.以此比較n-1次，數組a就按照從小到大的順序排好了。(也可以判斷是否有交換發生，如果一趟比較沒有發生交換，則表示數組a已經排好序)。

冒泡排序的java實現如下：

public static void bubbleSort(int[] elements){

for(int i = elements.length-1; i > 0; i--){

for(int j = 0; j < i;j++){

if(elements[j] > elements[j+1]){

swap(elements,j,j+1);//交換兩個元素

}

}

}

}

private static void swap(int[] elements,int i,int j){

int temp = elements[i];

elements[i] = elements[j];

elements[j] = temp;

}

冒泡排序的實現較為簡單，時間復雜度為O(n*n)，空間復雜度為O(1)。

另一種經典的交換排序是快速排序，快速排序的效率很高，但是空間復雜度較大，因為快速排序使用了遞歸，而遞歸的實現需要一個棧。快速排序的算法思想是：(假設數據存放在數組a[n]中)

1.如果待比較的數組長度為0或者1，則不用比較，直接返回。

2.如果待比較的數組長度大于1，則隨機的選擇一個中樞值(centrum)，然后分別從數組的兩端開始遍歷，并且把從左邊遍歷找到的大于centrum的元素和從右邊遍歷找到的小于centrum的元素進行交換，直到數組遍歷完畢(即：左邊遍歷指針指向的索引大于或等于右邊遍歷指針指向的索引)。

3.交換中樞元素和右邊遍歷指針指向的元素，這樣原來的數組以中樞元素為界分成了兩個數組，且左邊數組的元素都不大于中樞，右邊數組的元素都不小于中樞，然后分別對兩個子數組分別進行快速排序。

快速排序的java實現如下：

public static void quickSort(int[] elements,int begin,int end){

if(begin < end){

int centrum = elements[begin];//選擇第一個元素作為中樞

int front = begin+1;

int back = end;

while(front <= back){

while((front <= end) && (elements[front] < centrum)) front++;

while((back >= begin) && (elements[back] > centrum)) back--;

if(front < back){

swap(elements,front,back);

}else{

break;

}

}

if(begin < back)

swap(elements,begin,back);

quickSort(elements,begin,back-1);

quickSort(elements,back+1,end);

}

}

private static void swap(int[] elements,int i, int j){

int temp = elements[i];

elements[i] = elements[j];

elements[j] = temp;

}

總結

以上是生活随笔為你收集整理的交换排序 java_java实现交换排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。