經典算法學習——直接選擇排序

經典算法學習——直接選擇排序

直接選擇排序和直接插入排序類似，都將數據分為有序區和無序區，所不同的是直接插入排序是將無序區的第一個元素直接插入到有序區以形成一個更大的有序區；而直接選擇排序是從無序區選一個最小的元素直接放到有序區的最後。示例代碼上傳至：https://github.com/chenyufeng1991/SelectSort

算法描述如下：
（1）初始時，數組全為無序區為a[0...n-1]。令i = 0。

（2）在無序區a[i...n-1]中選取一個最小的元素，將其與a[i]交換。交換之後a[0...i]就形成了一個有序區。

（3）i++並重復第二步，直到i == n-1,排序完成。

實現如下：

//
//  main.c
//  SelectSort
//
//  Created by chenyufeng on 16/2/3.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include 

void selectSort(int *a,int n);
void swap(int *a,int *b);

int main(int argc, const char * argv[]) {


    int a[] = {6,1,4,9,0,3};
    selectSort(a,6);
    for (int i = 0; i < 6 ; i++) {
        printf("%d ",a[i]);
    }

    return 0;
}

void selectSort(int *a,int n){

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

        minIndex = i;
        //從無序區中找出最小的數
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                //不斷記錄最小數的下標；
                minIndex = j;
            }
        }
        //把無序區中最小的數放到有序區的最後一個位置；
        swap(&a[i],&a[minIndex]);
    }
}

void swap(int *a,int *b){

    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}