ヒルの並べ替えヒープを挿入し、泡が出てきます。
http://jingyixiao.com/?p=82
1、挿入順序：N番目の要素を遍歴する時、前のN-1個の要素はすでに順序付けされています。前のN-1個の要素を探して、このN番目の要素を適切な位置に置いて、シーケンスの要素を遍歴するまで続けます。その複雑さは計算しやすいです。一つ目は1、二つ目は2、N列は1＋2＋…＋NアルゴリズムのC実装です。
//並べ替えを挿入する(プログラムの抜粋:http://c.chinaitlab.com/c/basic/200905/785194.html)
void InsertSort(int array[], int length){
int i, j, key;
for (i = 1; i < length; i++){
key = array[i];
// i array[i]
for (j = i - 1; j >= 0 && array[j] > key; j--) {
array[j + 1] = array[j];
}
//
array[j + 1] = key;
}
}// shell （ ：http://c.chinaitlab.com/c/basic/200905/785198.html）
void ShellSort(int array[], int length){
int temp;
// , （ ， ～～～）
for (int increment = length / 2; increment > 0; increment /= 2)
for (int i = increment; i < length; ++i){
temp = array[i];
// increment
for (int j = i; j >= increment; j -= increment){
// i array[i]
if (temp < array[j - increment]) {
array[j] = array[j - increment];
}
else{
break;
}
}
//
array[j] = temp;
}
}注意点：このアルゴリズムの精髄はここでfor（int j=i；j>=increment；j-=increment）です。歩幅を使って少しずつ減らして、分かります。読めません。落ち着いて見てください。とりあえずここまで話しましょう。ちょっと眠いです。また今度来ます。
3、積み重ねるべきです。並べ替えました。
ヒープの定義:
n個のキーワードシーケンスKl，K 2，…，Knはヒープと呼ばれ、そのシーケンスが以下のような性質（ヒープ特性と略称する）を満たす場合のみ：
（1）ki≦K 2 iかつki≦K 2 i＋1または（2）Ki≧K 2 iかつki≧K 2 i＋1（1≦i≦）
このシーケンスに格納されているベクトルR［1…n］を完全な二叉樹の記憶構造と見なすと、スタックは実質的に以下の性質を満たす完全な二叉樹である。ツリーのいずれかの非葉結点のキーワードは、その左右の子供（存在すれば）結点のキーワードよりも大きくない（またはそうでない）。
スタックのこの性質は、1つのシーケンスの中の最小（大）の要素を迅速に位置決めできるようにする。
積み上げアルゴリズムのプロセスは以下の通りです。1）現在のシーケンスの最小（大きい）要素を得る2）この要素と最後の要素を交換すると、現在の最小（大きい）元素はシーケンスの最後に置いています。元の最後の要素はシーケンスの一番前に置いています。（この時のシーケンスは一番後ろに置いた要素を除くため）シーケンスを調整し、上の山の性質に満足させる必要があります。上の手順を繰り返し、シーケンス調整が完了するまで繰り返します。
/*
* FileName: HeapSort.cpp
* Type: C++
* Copyright: (c) 2009 Jingyi Xiao
* Authors: Jingyi Xiao
* Description:
*/
int MakeHeap (int * str, int i, int n){
int tmp, child;
for (tmp = str[i]; i*2+1 < n; i = child){ // ，
child = i * 2 + 1;
str[child] < str[child+1] ;
child != n-1 ? child++ : child;
if (tmp < str[child]) str[i] = str[child]; else break;
}
str[i] = tmp;
}
int HeapSort (int * narray, int n){
for (int i = n/2; i >= 0; i--)
MakeHeap(narray, i, n); // ， i=n/2
for (int i = n-1; i >= 0; i--){ // ～～～
swap (narray[0], narray[i]);
MakeHeap(narray, 0, i);
}
// output
for (int i = 0; i < n; i++) cout << narray[i] << ' ';
cout << endl;
return 0;
}
/*
* EOF
*//*
* FileName: BubbleSort.cpp
* Type: C++
* Copyright: (c) 2009 Jingyi Xiao
* Authors: Jingyi Xiao
* Description:
*/
using namespace std;
int BubbleSort (int * narray, int n){
int stop;
for (int i = 0; i < n; i++){
stop = 1;
for (int j = i+1; j < n; j++)
if (narray[i] > narray[j]) {
swap(narray[i], narray[j]);
stop = 0;
}
if (stop == 1) break;
}
// output
for (int i = 0; i < n; i++) cout << narray[i] << ' ';
cout << endl;
return 0;
}
/*
* FileName: QuikSort.cpp
* Type: C++
* Copyright: (c) 2009 Jingyi Xiao
* Authors: Jingyi Xiao
* Description:
*/
using namespace std;
int Qajust (int *str, int start, int end){
int deadline = str[start]; //
while (start < end){ // ， ！
while (start < end && str[end] >= deadline) --end;
swap (str[end], str[start]);
while (start < end && str[start] < deadline) ++start;
swap (str[start], str[end]);
}
return start;
}
int QuikSortDo(int *str, int start, int end){
if (start < end){ // ～
int pos = Qajust(str, start, end);
QuikSortDo(str, start, pos);
QuikSortDo(str, pos+1, end);
}
}
int QuikSort (int * narray, int n){
QuikSortDo(narray, 0, n); //
// output
for (int i = 0; i < n; i++) cout << narray[i] << ' ';
cout << endl;
return 0;
}
/*
* FileName: MergeSort.cpp
* Type: C++
* Copyright: (c) 2009 Jingyi Xiao
* Note: This source file is NOT a freeware
* Authors: Jingyi Xiao
* Description:
*/
using namespace std;
int MergeNow(int *str, int start, int mid, int end){
int str1[20], str2[20];
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
for (int i = 0; i < n1; i++) str1[i] = str[start+i]; //
for (int i = 0; i < n2; i++) str2[i] = str[mid+i+1];
str1[n1] = str2[n2] = 99999; //
for (int k = start, i = 0, j = 0; k <= end; k++){
if (str1[i] <= str2[j]) str[k] = str1[i++]; // ，
else str[k] = str2[j++];
}
}
int MergeSortDo(int *str, int start, int end){
if (start < end){ //
int pos = (start + end) / 2;
MergeSortDo(str, start, pos);
MergeSortDo(str, pos+1, end);
MergeNow(str, start, pos, end);
}
}
int MergeSort (int *narray, int n){
MergeSortDo(narray, 0, n); //
// output
for (int i = 0; i < n; i++) cout << narray[i] << ' ';
cout << endl;
return 0;
}