アルゴリズム導論c++実現第一章
1321 ワード
選択ソートの実装
ソートの考え方:
無秩序配列シーケンスはA[0...n]で記述する
Aのある位置をposで記述し、key=A[pos]、アルゴリズム思想は配列Aを遍歴し(位置1から)、A[pos-1]並べ替えられた配列A[0...pos-1]では、A[pos]=keyであり、keyA[0...pos]を秩序化する
ソートの考え方:
無秩序配列シーケンスはA[0...n]で記述する
Aのある位置をposで記述し、key=A[pos]、アルゴリズム思想は配列Aを遍歴し(位置1から)、A[pos-1]
#include
using namespace std;
/*
arr[1..n-1]， arr[0] ，
arr[0] arr[1] ， ，
， key ， key
*/
void selectSort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int j = i - 1;
int key = arr[i];
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
void selectSortTest() {
int arr[] = {5, 2, 4, 6, 1, 3};
cout << "Before sort: " << endl;
for (int i = 0; i < 6; i++) {
cout << i << ": " << arr[i] << endl;
}
cout << "After sort: " << endl;
selectSort(arr, 6);
for (int i = 0; i < 6; i++) {
cout << i << ": " << arr[i] << endl;
}
}
int main() {
selectSortTest();
return 0;
}