柚子快報(bào)激活碼778899分享：算法 Java：選擇排序

http://yzkb.51969.com/

目錄

直接選擇排序

?堆排序

基本思想：

每一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。

直接選擇排序

思路1：

在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素若它不是這組元素中的最后一個(gè)(第一個(gè))元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個(gè)元素

?

//選擇排序

/**

* 時(shí)間復(fù)雜度：O(N^2) 和數(shù)據(jù) 是否有序無關(guān)

* 空間復(fù)雜度：O(1)

* 穩(wěn)定性：不穩(wěn)定

* @param array

*/

public static void selectSort(int[] array){

for (int i = 0; i < array.length; i++) {

int minIndex = i;

for (int j = i+1; j < array.length; j++) {

if(array[j] < array[minIndex]){

minIndex = j;

}

}

swap(array,i,minIndex);

}

}

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

?思路2：

定義left和right分別去找最大值和最小值對應(yīng)的下標(biāo)找到后進(jìn)行交換一開始最大值和最小值下標(biāo)均為left，為0

?

private static void swap(int[] array, int i, int minIndex) {

int tmp = array[i];

array[i] = array[minIndex];

array[minIndex] = tmp;

}

public static void selectSort1(int[] array){

int left = 0;

int right = array.length-1;

while(left < right){

int minIndex = left;

int maxIndex = left;

for (int i = left+1; i <= right; i++) {

if(array[i] < array[minIndex]){

minIndex = i;

}

if(array[i] > array[maxIndex]){

maxIndex = i;

}

}

swap(array, left, minIndex);

//確保最大值的位置，最大值正好是 left 下標(biāo)

//此時(shí)把最大值換到了minIndex下標(biāo)

if(maxIndex == 0){

maxIndex = minIndex;

}

swap(array, right, maxIndex);

left++;

right--;

}

}

?堆排序

這里我們選擇大根堆進(jìn)行輸出，首先通過向下調(diào)整來進(jìn)行創(chuàng)建大根堆。

public static void createHeap(int[] array){

for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {

siftDown(array,parent,array.length);//向下調(diào)整，創(chuàng)建大根堆

}

}

public static void siftDown(int[] array, int parent, int length) {

int child = 2*parent+1;

while(child < length){

if(child + 1 < length && array[child] < array[child +1]){

child++;

}

if(array[child] > array[parent]){

swap(array, child, parent);

parent = child;

child = 2*parent+1;

}else{

break;

}

}

?然后再對大根堆進(jìn)行輸出，完整代碼如下：

public static void heapSort(int[] array){

createHeap(array);

int end = array.length-1;

while(end > 0){

swap(array, 0 ,end);

siftDown(array, 0,end);

end--;

}

}

public static void createHeap(int[] array){

for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {

siftDown(array,parent,array.length);//向下調(diào)整，創(chuàng)建大根堆

}

}

public static void siftDown(int[] array, int parent, int length) {

int child = 2*parent+1;

while(child < length){

if(child + 1 < length && array[child] < array[child +1]){

child++;

}

if(array[child] > array[parent]){

swap(array, child, parent);

parent = child;

child = 2*parent+1;

}else{

break;

}

}

}

柚子快報(bào)激活碼778899分享：算法 Java：選擇排序

http://yzkb.51969.com/

相關(guān)文章