ヒル、集計ソートC++アルゴリズム実装
1日に1つのアルゴリズムで、アルゴリズムの詳細を思い出しながら、C++を拾い返し、実験的なプログラムで、記念に残します.
挿入ソートには、直接挿入ソート、ヒルソート、集計ソートが含まれます.ソートアルゴリズムを直接挿入し、配列を2つに分割します.「シーケンスブロック」と「無秩序配列ブロック」は、無秩序配列から要素を取り出し、配列を充填する適切な位置に挿入します.つまり、ソートを完了します.最大の欠点は、配列要素を移動することです.
ヒルソートには「縮小増分ソート法」という考え方が加わっており、増分取法はcount/2、(count/2)/2、...、1. ヒルアルゴリズムは以下のように実現される.
集計ソートは、配列をできるだけ原子レベルに分けることです.2つ目は、原子レベルの数を2つ並べて並べ替え、結果を生成することです.
2つの秩序数列のマージについては、2つの数列の最初の数を比較するだけで、小さい人はまず誰を臨時キューに配置し、取った後、対応する数列のこの数を削除し、1つの数列が空になるまで、もう1つの数列のデータを順次取り出すことができます.
挿入ソートには、直接挿入ソート、ヒルソート、集計ソートが含まれます.ソートアルゴリズムを直接挿入し、配列を2つに分割します.「シーケンスブロック」と「無秩序配列ブロック」は、無秩序配列から要素を取り出し、配列を充填する適切な位置に挿入します.つまり、ソートを完了します.最大の欠点は、配列要素を移動することです.
ヒルソートには「縮小増分ソート法」という考え方が加わっており、増分取法はcount/2、(count/2)/2、...、1. ヒルアルゴリズムは以下のように実現される.
#include
using namespace std;
int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);
void shellSort(int * arrs){
int step = arrLen / 2; //
while(step > 0){
//
for(int i = step; i < arrLen; i++){
int temp = arrs[i];
int j;
// ,
for(j = i-step; j>=0 && temp < arrs[j]; j=j-step)
// ,
arrs[j+step]=arrs[j];
arrs[j+step]=temp;
}
step /= 2;
}
}
int main()
{
shellSort(arrs);
for (int i = 0; i < arrLen; i++)
cout << arrs[i] << endl;
return 0;
}
集計ソートは、配列をできるだけ原子レベルに分けることです.2つ目は、原子レベルの数を2つ並べて並べ替え、結果を生成することです.
2つの秩序数列のマージについては、2つの数列の最初の数を比較するだけで、小さい人はまず誰を臨時キューに配置し、取った後、対応する数列のこの数を削除し、1つの数列が空になるまで、もう1つの数列のデータを順次取り出すことができます.
#include
using namespace std;
int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);
int * tempArr = new int[arrLen];
void mergeArray(int * arrs, int * tempArr, int left, int middle, int right){
int i = left, j = middle ;
int m = middle + 1, n = right;
int k = 0;
while(i <= j && m <= n){
if(arrs[i] <= arrs[m])
tempArr[k++] = arrs[i++];
else
tempArr[k++] = arrs[m++];
}
while(i <= j)
tempArr[k++] = arrs[i++];
while(m <= n)
tempArr[k++] = arrs[m++];
for(i=0; i < k; i++)
arrs[left + i] = tempArr[i];
}
void mergeSort(int * arrs, int * tempArr, int left, int right){
if(left < right){
int middle = (left + right)/2;
mergeSort(arrs, tempArr, left, middle);
mergeSort(arrs, tempArr, middle + 1, right);
mergeArray(arrs, tempArr, left, middle, right);
}
}
int main()
{
mergeSort(arrs, tempArr, 0, arrLen-1);
for (int i = 0; i < arrLen; i++)
cout << arrs[i] << endl;
return 0;
}