直接選擇排序

鎖定

// elemtype 為所需排序的類型


void SelectSort(elemtype R[], int n) {
    int i, j, m;
    elemtype t;
    for (i = 0; i < n - 1; i++) {
        m = i;
        for (j = i + 1; j < n; j++)
            if (R[j] < R[m]) m = j;
        if (m != i) {
            t = R[i];
            R[i] = R[m];
            R[m] = t;
        }
    }
}

private static void SelectionSort(int[] numbers, int length) {
    for (int i = 0; i < length - 1; i++) {
        int temp = i;
        for (int j = i + 1; j < length; j++)
            if (numbers[j] < numbers[temp]) temp = j;
        if (temp != i) Swap(numbers, i, temp);
    }
}

# selectionSort
def findSmallest(arr):  # 找出數組中最小元素的函數
    smallest = arr[0]  # 將arr數組中的第一個元素作為最小值的初始化值
    smallest_index = 0  # 對應上行代碼，初始化存儲最小元素的索引
    for i in range(1,len(arr)):  # 從數組中第二個元素開始遍歷
        if smallest > arr[i]:
            smallest = arr[i]
            smallest_index = i
    return smallest,smallest_index

def selectionSort(arr):
    newArr = []  # 定義新生成數組的類型以及分配內存空間
   for i in range(len(arr)):
        smallest,smallest_index = findSmallest(arr)
        newArr.append(smallest)  # 將每次得到的最小元素加在數組後面
        arr.pop(smallest_index)  # 刪除原數組中已經被查找出來的最小元素
    return newArr

# 示例：
arr = [3,4,7,1,9,3,0,5]
newArr = selectionSort(arr)
print("經過選擇排序算法排序過後的序列為：{0}".format(newArr))
# 選擇排序後的序列為[0, 1, 3, 3, 4, 5, 7, 9]

//為了使用Random類，需要加入如下這行：
import java.util.*;
/**
 * 直接選擇排序算法的Java實現。<br/>
 *   1：從a[0]-a[N-1]中選出最小的數據，然後與a[0]交換位置<br/>
 *   2：從a[1]-a[N-1]中選出最小的數據，然後與a[1]交換位置（第1步結束後a[0]就是N個數的最小值）<br/>
 *   3：從a[2]-a[N-1]中選出最小的數據，然後與a[2]交換位置（第2步結束後a[1]就是N-1個數的最小值）<br/>
 *   以此類推，N-1次排序後，待排數據就已經按照從小到大的順序排列了。<br/>
 * 此代碼作為課件提供給學生參考，在學完數組、循環、判斷後練習。<br/>
 * @author luo_wenqiang@126點com
 * @version 1.0.0
 */
public class 直接選擇排序
{
    public static void main(String[] args) 
    {
        //聲明一個數組
        int[] array = new int[10];
        //為這個數組隨機填入整型數字
        Random random = new Random();
        for (int i = 0; i < array.length ; i++)
        {
            array[i] = random.nextInt(500);
        }
 
        System.out.print("原始數組  ：");
        System.out.println(Arrays.toString(array));
        /****************************************
         下面開始正式的“直接選擇排序”算法
         直接選擇排序的關鍵：
            1：從a[0]-a[N-1]中選出最小的數據，然後與a[0]交換位置
            2：從a[1]-a[N-1]中選出最小的數據，然後與a[1]交換位置（第1步結束後a[0]就是N個數的最小值）
            3：從a[2]-a[N-1]中選出最小的數據，然後與a[2]交換位置（第2步結束後a[1]就是N-1個數的最小值）
            以此類推，N-1次排序後，待排數據就已經按照從小到大的順序排列了。
         ****************************************/
         //N個數組元素，就需要循環N輪
         for(int i = 0; i < array.length-1; i++){
             //最小數的索引，該索引每次都根據外層循環的計數器來覺得初始值。
             int minIndex = i;
             for (int j = i + 1; j < array.length; j++)
             {
                 //根據最小數的索引，判斷當前這個數是否小於最小數。
                 //如果小於，則把當前數的索引作為最小數的索引。
                 //否則不處理。
                 if(array[minIndex] > array[j]){
                     minIndex = j;
                 }
                 //直到循環完成的時候，minIndex肯定就是當前這輪循環中，最小的那個。
             }
             //System.out.print(i + "輪，最小數" + array[minIndex] + "，");
             //System.out.print("原索引" + minIndex + "，新索引" + i);
             //得到最小數的索引後，把該索引對應的值放到最左邊，並且把最左邊的值放到索引所在的位置.
             //最左邊的值
             int temp = array[i];
             //把最小數索引對應的值放到最左邊
             array[i] = array[minIndex];
             //把原來最左邊對應的值放到最小數索引所在的位置
             array[minIndex] = temp;
             System.out.println(String.format("%2s",(i + 1)) + "輪排序後：" + Arrays.toString(array));
         }
    }
}
python 實現
def select_sort(lists):
    print 'input lists: ', lists
    count = len(lists) - 1    
    for i in range(count):        
        min_index = i        
        for j in range(i+1, count):
            if lists[min_index] > lists[j]:
                min_index = j
        lists[min_index], lists[i] = lists[i], lists[min_index]   
        print i+1, ' times, result is', lists 
    return lists
tmp_b = [2, 6, 8, 1, 5, 21, 0, 5, 3, 7]
select_sort(tmp_b)
程序輸出為：
input lists:  [2, 6, 8, 1, 5, 21, 0, 5, 3, 7]
#第一次， 2 和 0 的位置調換，最小的值放到列表的最左側
1  times, result is [0, 6, 8, 1, 5, 21, 2, 5, 3, 7]
#第二次， 1 和 6 的位置調換
2  times, result is [0, 1, 8, 6, 5, 21, 2, 5, 3, 7]
3  times, result is [0, 1, 2, 6, 5, 21, 8, 5, 3, 7]
4  times, result is [0, 1, 2, 3, 5, 21, 8, 5, 6, 7]
5  times, result is [0, 1, 2, 3, 5, 21, 8, 5, 6, 7]
6  times, result is [0, 1, 2, 3, 5, 5, 8, 21, 6, 7]
7  times, result is [0, 1, 2, 3, 5, 5, 6, 21, 8, 7]
8  times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]
9  times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]
10  times, result is [0, 1, 2, 3, 5, 5, 6, 7, 8, 21]