选择排序Linux上c 实现

选择排序Linux下c 实现

        选择排序，将待排序序列分为两个序列：已排序序列和未排序序列。每次从未排序序列中，选择一个最小的元素，存放在到已排序序列的最后，直到所有元素排序完毕。关键代码如下：

        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值较小时，选择排序比冒泡排序快。