程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 選擇排序Linux下c 實現

選擇排序Linux下c 實現

編輯：C++入門知識

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

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

[cpp]
#ifndef SELECTSORT_H
#define SELECTSORT_H
extern void selectSort(int *pArr, const int length);
#endif

#ifndef SELECTSORT_H
#define SELECTSORT_H www.2cto.com
extern void selectSort(int *pArr, const int length);
#endif
2、選擇排序源文件：selectSort.c

[cpp]
#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;
                }
        }
}

#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

[cpp]
#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

#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

[cpp]
#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;
        }
}

#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、編譯程序：

[cpp]
[root@localhost selectSort]$ gcc -c main.c
[root@localhost selectSort]$ gcc -c selectSort.c
[root@localhost selectSort]$ gcc -o main main.o selectSort.o

[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，大致如下：

[cpp]
[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

[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值較小時，選擇排序比冒泡排序快。