選擇排序Linux下C實現

選擇排序，將待排序序列分為兩個序列：已排序序列和未排序序列。每次從未排序序列中，選擇一個最小的元素，存放在到已排序序列的最後，直到所有元素排序完畢。關鍵代碼如下：

1、選擇排序頭文件：selectSort.h

1. #ifndef SELECTSORT_H   
2. #define SELECTSORT_H   
3. extern void selectSort(int *pArr, const int length);  
4. #endif  

2、選擇排序源文件：selectSort.c

1. #include "selectSort.h"   
2. void selectSort(int *pArr, const int length)  
3. {  
4.         int i,j,min,tmp;  
5.         for(i=0; i<length-1; i++)  
6.         {  
7.                 min =i;  
8.                 for(j=i+1; j<length; j++)  
9.                 {  
10.                         if(*(pArr+min)>*(pArr+j))  
11.                         {  
12.                                 min=j;  
13.                         }  
14.                 }  
15.                 if(min!=i)  
16.                 {  
17.                         tmp=*(pArr+i);  
18.                         *(pArr+i)=*(pArr+min);  
19.                         *(pArr+min)=tmp;  
20.                 }  
21.         }  
22. }  

3、main頭文件：main.h

1. #ifndef MAIN_H   
2. #define MAIN_H   
3. #include<stdio.h>   
4. #include "selectSort.h"   
5. int main(void);  
6. void showArr(const int *pArr, const int length);  
7. void initRandomArr(int *pArr, const int length);  
8. #endif  

4、main源文件：main.c

1. #include "main.h"   
2.   
3. int main(void)  
4. {  
5.         printf("Input array length:\n");  
6.         int length;  
7.         scanf("%d", &length);  
8.         if(length<0)  
9.         {  
10.                 printf("Array length must be larger 0\n");  
11.                 return 1;  
12.         }  
13.         int arr[length];  
14.         initRandomArr(arr, length);  
15.         printf("Get random array :\n");  
16.         showArr(arr, length);  
17.         selectSort(arr, length);  
18.         printf("select sort result:\n");  
19.         showArr(arr, length);  
20.         return 0;  
21. }  
22. void showArr(const int *pArr, const int length)  
23. {  
24.         int i;  
25.         for(i=0; i<length; i++)  
26.         {  
27.                 printf("%d ", *(pArr+i));  
28.         }  
29.         printf("\n");  
30. }  
31. void initRandomArr(int *pArr, const int length)  
32. {  
33.         int i;  
34.         srand(time(NULL));  
35.         for(i=0; i< length; i++)  
36.         {  
37.                 *(pArr+i)=rand()%1000;  
38.         }  
39. }  

5、編譯程序：

1. [root@localhost selectSort]$ gcc -c main.c  
2. [root@localhost selectSort]$ gcc -c selectSort.c  
3. [root@localhost selectSort]$ gcc -o main main.o selectSort.o  

執行可執行文件main，大致如下：

1. [root@localhost selectSort]$ ./main   
2. Input array length:  
3. 8  
4. Get random array :  
5. 906 968 161 208 757 885 370 691   
6. select sort result:  
7. 161 208 370 691 757 885 906 968   

選擇排序時間復雜度О(n²)， 交換次數O(n)，已經有序的最好情況下，交換0次；逆序的最壞情況下，交換n-1次。 交換次數比冒泡排序少多了，由於交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快 http://www.linuxidc.com/Linux/2012-03/55662.htm。