挿入ソートの「折半挿入ソート」(C++実装)
1185 ワード
定義#テイギ#
直接挿入ソートは秩序領域を生成するため、折半ルックアップ法を使用して挿入の位置を見つけることができます.このような挿入ソートは折半挿入ソートと呼ばれます.したがって、折半挿入には要素サイズの整列(大きいものから小さいものまで、または小さいものから大きいものまで)が重要です.
インプリメンテーション
まとめ
折り返し挿入ソート時に直接挿入ソートのアップグレード版
直接挿入ソートは秩序領域を生成するため、折半ルックアップ法を使用して挿入の位置を見つけることができます.このような挿入ソートは折半挿入ソートと呼ばれます.したがって、折半挿入には要素サイズの整列(大きいものから小さいものまで、または小さいものから大きいものまで)が重要です.
インプリメンテーション
#include
using namespace std;
void binInsertSort(int R[], int n)
{
int i, j, low, high, mid;
int tmp;
for (i = 1; i < n; i++)
{
if (R[i] < R[i - 1])
{
tmp = R[i];
low = 0;
high = i - 1;
while (low <= high)//
{
mid = (low + high) / 2;
if (tmp < R[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (j = i - 1; j >= high + 1; j--)//
{
R[j + 1] = R[j];
}
R[high + 1] = tmp;// tmp
}
}
}
int main()
{
int R[] = { 8,6,1,3,4,9 };
binInsertSort(R, 6);
for (int i = 0; i < 6; i++)
{
cout << R[i] << " ";
}
return 0;
}
まとめ
折り返し挿入ソート時に直接挿入ソートのアップグレード版