數據結構 - 簡單選擇排序(simple selection sort)
選擇排序(selection sort) : 每一趟在n-i+1個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄.
簡單選擇排序(simple selection sort) : 通過n-i次關鍵字之間的比較, 從n-i+1個記錄中選出關鍵字最小的記錄, 並和第i個記錄交換.
選擇排序需要比較n(n-1)/2次, 即(n-1)+(n-2)+...+1 = [(n-1)+1](n-1)/2次, 時間復雜度是O(n^2).
簡單選擇排序的主要步驟是: 1. 選出較小元素的位置. 2. 交換.
代碼:
/*
* SimpleSelectionSort.cpp
*
* Created on: 2014.6.5
* Author: Spike
*/
#include
#include
void print(const std::vector& L) {
for (auto i : L) {
std::cout << i << ;
}
std::cout << std::endl;
}
int SelectMinKey(std::vector& L, const size_t p) {
int min = p;
for (size_t i=p+1; i& L) {
for (size_t i=0; i L = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
SelectSort(L);
print(L);
}
輸出:
4 38 65 97 76 13 27 49 55 49
4 13 65 97 76 38 27 49 55 49
4 13 27 97 76 38 65 49 55 49
4 13 27 38 76 97 65 49 55 49
4 13 27 38 49 97 65 76 55 49
4 13 27 38 49 49 65 76 55 97
4 13 27 38 49 49 55 76 65 97
4 13 27 38 49 49 55 65 76 97
4 13 27 38 49 49 55 65 76 97
4 13 27 38 49 49 55 65 76 97
4 13 27 38 49 49 55 65 76 97
