选择排序,将待排序序列分为两个序列:已排序序列和未排序序列。每次从未排序序列中,选择一个最小的元素,存放在到已排序序列的最后,直到所有元素排序完毕。关键代码如下:
1、选择排序头文件:selectSort.h
#ifndef SELECTSORT_H
#define SELECTSORT_H
extern void selectSort(int *pArr, const int length);
#endif
2、选择排序源文件:selectSort.c
#include "selectSort.h"
void selectSort(int *pArr, const int length)
{
int i,j,min,tmp;
for(i=0; i<length-1; i++)
{
min =i;
for(j=i+1; j<length; j++)
{
if(*(pArr+min)>*(pArr+j))
{
min=j;
}
}
if(min!=i)
{
tmp=*(pArr+i);
*(pArr+i)=*(pArr+min);
*(pArr+min)=tmp;
}
}
}
3、main头文件:main.h
#ifndef MAIN_H
#define MAIN_H
#include<stdio.h>
#include "selectSort.h"
int main(void);
void showArr(const int *pArr, const int length);
void initRandomArr(int *pArr, const int length);
#endif
4、main源文件:main.c
#include "main.h"
int main(void)
{
printf("Input array length:\n");
int length;
scanf("%d", &length);
if(length<0)
{
printf("Array length must be larger 0\n");
return 1;
}
int arr[length];
initRandomArr(arr, length);
printf("Get random array :\n");
showArr(arr, length);
selectSort(arr, length);
printf("select sort result:\n");
showArr(arr, length);
return 0;
}
void showArr(const int *pArr, const int length)
{
int i;
for(i=0; i<length; i++)
{
printf("%d ", *(pArr+i));
}
printf("\n");
}
void initRandomArr(int *pArr, const int length)
{
int i;
srand(time(NULL));
for(i=0; i< length; i++)
{
*(pArr+i)=rand()%1000;
}
}
5、编译程序:
[root@localhost selectSort]$ gcc -c main.c
[root@localhost selectSort]$ gcc -c selectSort.c
[root@localhost selectSort]$ gcc -o main main.o selectSort.o
执行可执行文件main,大致如下:
[root@localhost selectSort]$ ./main
Input array length:
8
Get random array :
906 968 161 208 757 885 370 691
select sort result:
161 208 370 691 757 885 906 968
选择排序时间复杂度О(n²), 交换次数O(n),已经有序的最好情况下,交换0次;逆序的最坏情况下,交换n-1次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。