選擇排序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"
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。