选择排序

  基本思想:选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大) 元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推, 直到所有元素均排序完毕。

动图演示

选择排序

C代码

#include<stdio.h>
void SelectSort(int *a, int n) {
    for (int i = 0; i < n; i++)
    {
        int key = i;    //    临时变量用于存放数组最小值的位置
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[key]) {    
                key = j;    //    记录数组最小值位置
            }
        }
            if (key != i)
            {
                int tmp = a[key]; a[key] = a[i]; a[i] = tmp;    //    交换最小值
            }

    }
}
int main() {
    int a[] = { 12,4,15,2,6,22,8,10,1,33,45,24,7 };
    int n = sizeof(a) / sizeof(int);
    SelectSort(a, n);
    printf("排序好的数组为: ");
    for (int k = 0; k < n; k++)
        printf("%d ", a[k]);
    printf("\n");
    return 0;
}

分析:

  最差、最优、平均时间复杂度都为O(n^2)。辅助空间为O(1)。稳定性:不稳定。

Copyright © liyang.com 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-01 15:22:50

results matching ""

    No results matching ""