算法描述

选择排序(Selection-sort) 是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。最好和最坏时间复杂度皆为O(n²)。
时间复杂度:O(n²)
空间复杂度:O(1)

排序过程

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

伪代码实现

void InsertionSort(elements, length){
    for(i = 1; i < length; i++){
        tmp = elements[i]
        for(j = i; j > 0; j--){
            if(elements[j - 1] > tmp)
                elements[j] = elements[j - 1]
            else
                break
        }
        elements[j] = tmp
    }
}

C语言实现

#include <stdio.h>
#define ARRSIZE(arr) (sizeof(arr) / sizeof(arr[0]))

void InsertionSort(int elements[], int length)
{
    //假设第0个元素已经是排好后的序列的元素
    for (int i = 1; i < length; i++)
    {
        //往回扫描,找到比elements[i]小的下标
        //并把比elements[i]大的元素后移一位
        int j;
        int tmp = elements[i];
        for (j = i; j > 0; j--)
        {
            //往回扫描,j代表从i递减到0的下标,就是已经排好的序列
            if (elements[j - 1] > tmp)
            {
                //如果比我大就把他往后挪,挪出一个空位
                //这里会占用掉elements[i],所以前面要先给他存起来
                elements[j] = elements[j - 1];
            }
            else
                break;//找到的插入位置就跳出
        }
        elements[j] = tmp;//插入元素
    }

}

int main(int argc, char const *argv[])
{
    int elems[] = {3, 4, 2, 1, 5, 9, 2, 1, 0, 22, 33, 5, 112, 11, 22, 55, 22, 61, 97};
    int len = ARRSIZE(elems);
    InsertionSort(elems, len);
    for (int i = 0; i < len; i++)
        printf("%4d", elems[i]);
    printf("\n");
    return 0;
}

程序输出

  0   1   1   2   2   3   4   5   5   9  11  22  22  22  33  55  61  97 112
Last modification:April 11th, 2020 at 10:27 am
If you think my article is useful to you, please feel free to appreciate