选择排序

维基百科,自由的百科全书
跳转至: 导航搜索
选择排序
選擇排序動畫演示
分類 排序算法
數據結構 數組
最差時間複雜度 О(n²)
最優時間複雜度 О(n²)
平均時間複雜度 О(n²)
最差空間複雜度 О(n) total, O(1) auxiliary

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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

C语言实现[编辑]

void selection_sort(int *a, int len)
{
    register int i, j, min, t;
    for(i = 0; i < len - 1; i ++)
    {
        min = i;//最小值下标
        //查找最小值
        for(j = i + 1; j < len; j ++)
            if(a[min] > a[j])
                min = j;
        //交换
        if(min != i)
        {
            t = a[min];
            a[min] = a[i];
            a[i] = t;
        }
    }
}

C语言实现2[编辑]

/*=============================================================================
#
#     FileName: selection_sort_in_c.c
#         Desc: 选择排序
#
#       Author: gavinyao
#        Email: gavinyao-tencent-com
#
#      Created: 2013-12-13 01:13:15
#      Version: 0.0.1
#      History:
#               0.0.1 | gavinyao | 2013-12-13 01:13:15 | initialization
#
=============================================================================*/
#include <stdio.h>
#include <stdlib.h> // rand sranddev
 
/**
 * @brief 选择排序
 *
 * @param list[] 要排序的数组
 * @param n 数组中的元素数量
 */
void selection_sort_0(int list[], int len)
{
    int i, j; // 用于循环
    int min_index; // 指向当前最小的哪个数
    int temp; // 用于交换
    int min; // 当前最小值
    //  最后一个不用排了, 所以 len - 1
    for (i = 0; i < len - 1; ++i)
    {
        // 最小值设置为当前值
        min = list[i];
        // k 指向当前最小的哪个位置
        min_index = i;
        // 找到剩下的元素中最小的
        for (j = i; j < len; ++j)
        {
            if (list[j] < min)
            {
                min = list[j];
                min_index = j;
            }
        }
        // 当前数不是最小的
        if (min_index > i)
        {
            // 把最小的数放到当前的位置
            temp = list[i];
            list[i] = min;
            list[min_index] = temp;
        }
 
    }
}
 
void selection_sort(int *list, int list_size)
{
    int i, j; // 用于循环
    int min_index; // 当前最小值的 index
    int temp; // 用于交换
    // 最后一个元素不用排了, 所以可以 len - 1; 少一次循环
    for (i = 0; i < list_size - 1; ++i)
    {
        // 假定当前的元素就是最小的
        min_index = i;
        // 查找剩下的元素当中最小的
        for (j = i; j < list_size; ++j)
        {
            if (list[j] < list[min_index])
            {
                min_index = j;
            }
        }
        // 如果找到了比当前小的, 就把当前元素与之交换
        if (min_index != i)
        {
            temp = list[i];
            list[i] = list[min_index];
            list[min_index] = temp;
        }
    }
}
 
/**
 * @brief 打印数组
 
*/
 
}
void print_array(int* list, int len)
{
	int i = 0;
	for (i = 0; i < len; i++)
	{
		printf("%d  ", list[i]);
	}
}
 
 
int main(void)
{
    /*
    int list[] = {1, 3, 4, 3, 5, 7, 9, 8, 0};
    int len = sizeof(list) / sizeof(list[0]);
    */
    int len = 40;
    int list[len];//vs2013会报错
    for (int i = 0; i < len; ++i)
    {
        //sranddev();
        //rand();
        list[i] = rand() % 1000;
    }
 
    print_array(list, len);
    selection_sort(list, len);
    print_array(list, len);
 
    return 0;
}

C++语言实现[编辑]

/*=============================================================================
#
#     FileName: selection_sort_in_cpp.cpp
#         Desc: 选择排序
#
#       Author: gavinyao
#        Email: gavinyao-tencent
#
#      Created: 2013-12-13 01:13:35
#      Version: 0.0.1
#      History:
#               0.0.1 | gavinyao | 2013-12-13 01:13:35 | initialization
#
=============================================================================*/
#include <iostream>
#include <vector>
#include <cstdlib> // rand, sranddev
 
using namespace std;
 
template<class T>
void SelectSort(vector<T> &vecList, int nLow, int nHigh)
{
    if (nLow > = nHigh)
        return;
    int i, j; // 用于循环
    int nMinIndex; // 指向最小的哪个
    T temp; // 用于交换
 
    // 最后一个就不用比了, 所以 nHigh - 1
    for (i = nLow; i < nHigh - 1; ++i)
    {
        // 假定当前元素是最小的
        nMinIndex = i;
        // 从剩下的元素中查找最小的
        for (j = i; j < nHigh; ++j)
        {
            if (vecList[j] < vecList[nMinIndex])
            {
                nMinIndex = j;
            }
        }
        // 如果找到与当前元素交换
        if (i != nMinIndex)
        {
            temp = vecList[i];
            vecList[i] = vecList[nMinIndex];
            vecList[nMinIndex] = temp;
        }
    }
}
 
template<class T>
void PrintVector(const vector<T> &vecList)
{
    for (int i = 0; i < vecList.size(); ++i)
    {
        cout << vecList[i] << '\t';
    }
    cout << endl;
}
 
int main(void)
{
 
    int len = 8;
    vector<int> vecIntList;
    for (int i = 0; i < len; ++i)
    {
        sranddev();
        vecIntList.push_back(rand() % 1000);
    }
    PrintVector(vecIntList);
    SelectSort(vecIntList, 0, vecIntList.size());
    PrintVector(vecIntList);
 
 
    return 0;
}

C#语言实现[编辑]

/// <summary>
/// 选择排序
/// </summary>
/// <param name="intArray">待排序数组</param>
static void SelectSort(int[] intArray)
{
    int intLength = intArray.Length,
        j = 0,
        k = 0,//位置记录
        temp = 0;//交换中间变量
    //循环intLength-1次得出排序结果
    for (int i = 0; i < intLength - 1; i++)
    {
        k = i;
        //在当前的无序区[i-intLength]中找出最小的值
        for (j = i + 1; j < intLength; j++)
        {
            if (intArray[j] < intArray[k])
            {
                k = j;//记录目前最小值的位置
            }
        }
        if (k != i)//k!=i,交换intArray[i]和intArray[k]
        {
            temp = intArray[i];
            intArray[i] = intArray[k];
            intArray[k] = temp;
        }
    }
}

Python语言实现[编辑]

def selection_sort(L):
    N = len(L)
    exchanges_count = 0
    for i in range(N-1):
        min_index = i
        for j in range(i+1, N):
            if L[min_index] > L[j]:
                min_index = j
        if min_index != i:
            L[min_index], L[i] = L[i], L[min_index]
            exchanges_count += 1
        print('iteration #{}: {}'.format(i, L))
    print('Total {} swappings'.format(exchanges_count))
    return L
 
testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
print('Before selection sort: {}'.format(testlist))
print('After selection sort:  {}'.format(selection_sort(testlist)))

Java语言实现[编辑]

public void selectSort(Comparable[] array) {
		System.out.println("===========Insert Sort Started===========");
		Comparable temp;
		//min存放最小元素的index
		int min;
		for (int index = 0; index < array.length - 1; index++) {
			//假定第一个元素为最小元素
			min = index;
			//循环遍历元素,每遍历一个元素,与当前最小元素比较,若此元素比当前最小元素小,则将此元素置为最小元素
			for (int time = index + 1; time < array.length; time++) {
				if (array[time].compareTo(array[min]) < 0) {
					min = time;
				}
			}
			//遍历一遍,找到一个最小元素,把此最小元素的index与min交换位置
			temp = array[index];
			array[index] = array[min];
			array[min] = temp;
		}
		System.out.println("The array after sorted....");
		System.out.println(Arrays.toString(array));
		System.out.println("============Insert Sort Ended============");
	}

复杂度分析[编辑]

选择排序的交换操作介于0(n-1)次之间。选择排序的比较操作n(n-1)/2次之间。选择排序的赋值操作介于03(n-1)次之间。


比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n\times(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

原地操作几乎是选择排序的唯一优点,当方度(space complexity)要求较高时,可以考虑选择排序;实际适用的场合非常罕见。

外部链接[编辑]