首页 > 代码库 > 【Algorithm】选择排序

【Algorithm】选择排序

2024-07-08 03:19:43   227人阅读

一. 算法描述

　　选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

　　举个例子：5 7 6 4 3 8

　　第一趟：  3 7 6 4 5 8

　　第二趟：  3 4 6 7 5 8

　　第三趟：  3 4 5 7 6 8 

　　第四趟：  3 4 5 6 7 8

　　第五趟：  3 4 5 6 7 8

二. 算法实现

#include<stdio.h>/** author：Knife* time：2014.06.13 11:17* algorithm：选择排序*/void main(){    int intArr[] = {8,3,6,4,2,9,5,4,1,7};    int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度    int minIndex,tmp;    // 选择排序    for(int i = 0; i < n-1; i++){        minIndex = i;        for(int j = i+1; j < n; j++){            if(intArr[j]<intArr[minIndex]){                minIndex = j;            }        }        if(minIndex != i){            tmp = intArr[minIndex];            intArr[minIndex] = intArr[i];            intArr[i] = tmp;        }    }    //打印输出    for(int i=0; i < n; i++){        printf("%d ", intArr[i]);    }    printf("\n");}

三. 算法分析

  • 平均时间复杂度：O(n2)
  • 空间复杂度：O(1)  (用于交换和记录索引)
  • 稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）

参考资料

[1] http://blog.csdn.net/cjf_iceking/article/details/7914554


联系
我们