10種類のソートアルゴリズムのまとめ(コードと説明)
13331 ワード
1.泡立ちソート
基本的な考え方は、隣接するレコードのキーワードを2つ比較し、逆シーケンスであれば交換することです.
バブルソート時間の複雑さが最も良い場合はO(n),最悪の場合はO(n^2)である.
改善構想1:フラグビットを設定し、明らかに交換(flag=false)が発生していない場合は、ソートが完了したことを示します.
改善構想2:一輪下りマークの最後の位置を記録し、次に頭部からこの位置まで遍歴するとOk.
元のバブルソートコードは次のとおりです.
2.考え方を改善する1:
3.思想を改善する2:
二.直接挿入ソート
順序付けされた順序付けテーブルにレコードを挿入し、レコード数が1増加した新しい順序付けテーブルを得る.
時間の複雑さもO(n^2)であり,発泡法や選択ソートよりも性能が優れている.
コードは次のとおりです.
三、簡単な選択順序
n-i次キーワード間の比較により、n-i+1個のレコードの中からキーワードの最小のレコードを選択し、i(1<=i<=n)番目のレコードと交換する
バブルソートと同様にO(n^2)であるが,単純にソートを選択する性能はバブルソートよりやや優れている.
コードは次のとおりです.
四、ヒルソート
まず、並べ替えられる要素のシーケンス全体をいくつかのサブシーケンス(増分要素からなる)に分割して直接挿入ソートし、次に増分を順次削減してソートします.シーケンス全体の要素が基本的に秩序化されている(増分が十分小さい)場合、全体の要素を直接挿入ソートします(増分は1).その時間的複雑さはO(n^3/2)であり,並べ替えられたO(n^2)を直接挿入するよりも優れている.
五、集計ソート
初期シーケンスがn個のレコードを含むと仮定すると、n個の秩序化されたサブシーケンスと見なすことができ、各サブシーケンスの長さは1であり、次いで2個の2個の2個の2個の2個の長さは2または1の秩序化されたサブシーケンスが得られ、さらに2個の2個の2個の結合が得られる.この並べ替え方法は、長さnの秩序化シーケンスが得られるまで、2ウェイ集計並べ替えと呼ばれる.時間的複雑度がO(nlogn)、空間的複雑度がO(n+logn)である、非再帰的に集計が実現されると、再帰時の深さがlognのスタック空間的複雑度がO(n)となることを回避する.
コード:
六、スタック並べ替えスタックは以下の性質を有する完全な二叉木である:各ノードの値はその左右の子供ノードの値より大きいか、または等しいか、大頂スタックと呼ばれる.あるいは、各ノードの値が左右の子供ノードの値以下であることを、小さなトップスタックと呼ぶ.
七:カウントソート
カウントソート(Counting sort)は安定したソートアルゴリズムである.カウントソートには、追加の配列Cが使用され、i番目の要素は、ソートされる配列Aの値がiに等しい要素の数である.次に配列Cに従ってAの要素を正しい位置に並べます.
アルゴリズムの手順は次のとおりです.ソートされる配列の最大および最小の要素 を見つける配列中の値iの各要素が出現する回数を統計し、配列Cのi番目の項目 に格納.すべてのカウントを加算(Cの位置が1の要素から、各項目と前の項目を加算) .ターゲット配列を逆充填する:各要素iを新しい配列のC(i)番目の項目に配置し、1つの要素を配置するたびにC(i)を1 減算する.
カウントのための配列
C
の長さは、ソート対象配列のデータの範囲(ソート対象配列の最大値と最小値の差に1を加算)に依存し、カウントソートはデータ範囲の広い配列に対して多くの時間とメモリを必要とする
八:バケツの並べ替え
バケツソート(Bucket sort)やいわゆる箱ソートは、配列を限られた数のバケツに分けることを原理とするソートアルゴリズムです.各バケツを個別に並べ替える(別の並べ替えアルゴリズムを再使用するか、バケツの並べ替えを再帰的に継続する可能性がある)
バケツのソートは、次の手順で行います.は、バケツとして定量的配列を設定する. シリアルを訪問し、プロジェクトを1つずつ対応するバケツに配置します.(hash) は、空でないバケツごとに並べ替えられる. 空ではないバケツからプロジェクトを元のシリアルに戻します.
九.ベースソート
基数ソート(英語:Radix sort)は、整数をビット数で異なる数字に切断し、各ビット数でそれぞれ比較することを原理とする非比較型整数ソートアルゴリズムである.整数は文字列(名前や日付など)や特定のフォーマットの浮動小数点数も表すことができるため、基数ソートは整数にのみ使用できるわけではありません.
これは、比較対象のすべての数値(正の整数)を同じ数桁の長さに統一し、数桁の短い数の前にゼロを補うことによって実現される.そして,最下位から順に1回ソートする.これにより、最下位のソートから最上位のソートが完了するまで、数列は秩序化されたシーケンスになります.
基数ソート方式はLSD(Least significant digital)またはMSD(Most significant digital)を用いることができ、LSDのソート方式はキー値の右端から始まり、MSDは逆にキー値の左端から始まる.
十.クイックソート
ソートする配列をA[0]......A[N-1]とし、まず任意に1つのデータ(通常は配列の最初の数)をキーデータとして選択し、それより小さい数をすべて前に置き、それより大きい数をすべて後ろに置くプロセスを高速ソートと呼ぶ.なお、高速ソートは安定したソートアルゴリズムではなく、すなわち、複数の同じ値の相対位置がアルゴリズムの終了時に変動する可能性がある.
原文住所:住所
基本的な考え方は、隣接するレコードのキーワードを2つ比較し、逆シーケンスであれば交換することです.
バブルソート時間の複雑さが最も良い場合はO(n),最悪の場合はO(n^2)である.
改善構想1:フラグビットを設定し、明らかに交換(flag=false)が発生していない場合は、ソートが完了したことを示します.
改善構想2:一輪下りマークの最後の位置を記録し、次に頭部からこの位置まで遍歴するとOk.
元のバブルソートコードは次のとおりです.
void swap(int left, int right)
{
left = left ^ right;
right = right ^ left;
left = left ^ right;
}
/*****************************************************************/
/* O(n), O(n^2)
* : , */
void BubbleSort(int arr[], int num)
{
int i, j;
for (i = 0; i < num; i++)
{
for (j = 1; j < num - i - 1; j++)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}
2.考え方を改善する1:
// ： ， （flag = flase)， .
void swap(int left, int right)
{
left = left ^ right;
right = right ^ left;
left = left ^ right;
}
void BubbleSort(int arr[], int num)
{
int k = num;
int j;
bool flag = true;
while (flag)
{
flag = false;
for (j = 1; j < k; j++)
{
if (arr[j] > arr[j + 1])
{
swap1(arr[j], arr[j + 1]);
flag = true;
}
}
k--;
}
}3.思想を改善する2:
// ： ， Ok
void BubbleSort3(int arr[], int num)
{
int k, j;
int flag = num;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
{
if (arr[j] > arr[j + 1])
{
swap1(arr[j], arr[j + 1]);
flag = j;
}
}
}
}二.直接挿入ソート
順序付けされた順序付けテーブルにレコードを挿入し、レコード数が1増加した新しい順序付けテーブルを得る.
時間の複雑さもO(n^2)であり,発泡法や選択ソートよりも性能が優れている.
コードは次のとおりです.
/* : , , 1
* O(n^2), */
void InsertionSort(int arr[], int num)
{
int temp;
int i, j;
for (i = 1; i < num; i++)
{
temp = arr[i];
for (j = i; j > 0 && arr[j - 1] > temp; j--)
arr[j] = arr[j - 1];
arr[j] = temp;
}
}三、簡単な選択順序
n-i次キーワード間の比較により、n-i+1個のレコードの中からキーワードの最小のレコードを選択し、i(1<=i<=n)番目のレコードと交換する
バブルソートと同様にO(n^2)であるが,単純にソートを選択する性能はバブルソートよりやや優れている.
コードは次のとおりです.
/* (simple selection sort) n-i , n-i+1
* , i(1<=i<=n)
* O(n^2), */
void swap(int left, int right)
{
left = left ^ right;
right = right ^ left;
left = left ^ right;
}
void SelectSort(int arr[], int num)
{
int i, j, Mindex;
for (i = 0; i for (j = i + 1; j if (arr[j] 四、ヒルソート
まず、並べ替えられる要素のシーケンス全体をいくつかのサブシーケンス(増分要素からなる)に分割して直接挿入ソートし、次に増分を順次削減してソートします.シーケンス全体の要素が基本的に秩序化されている(増分が十分小さい)場合、全体の要素を直接挿入ソートします(増分は1).その時間的複雑さはO(n^3/2)であり,並べ替えられたO(n^2)を直接挿入するよりも優れている.
/* : （ “ ” ）
， ， （ ） ，
（ 1）。 O(n^3/2), O(n^2) */
void ShellSort(int *arr, int N)
{
int i, j, increment;
int tmp;
for (increment = N / 2; increment > 0; increment /= 2)
{
for (i = increment; i < N; i++)
{
tmp = arr[i];
for (j = i; j >= increment; j -= increment)
{
if (arr[j - increment] > tmp)
arr[j] = arr[j - increment];
else
break;
}
arr[j] = tmp;
}
}
}五、集計ソート
初期シーケンスがn個のレコードを含むと仮定すると、n個の秩序化されたサブシーケンスと見なすことができ、各サブシーケンスの長さは1であり、次いで2個の2個の2個の2個の2個の長さは2または1の秩序化されたサブシーケンスが得られ、さらに2個の2個の2個の結合が得られる.この並べ替え方法は、長さnの秩序化シーケンスが得られるまで、2ウェイ集計並べ替えと呼ばれる.時間的複雑度がO(nlogn)、空間的複雑度がO(n+logn)である、非再帰的に集計が実現されると、再帰時の深さがlognのスタック空間的複雑度がO(n)となることを回避する.
コード:
/* n , n , 1,
* , ( n/2 ) 2 1 , ,...
* , n , 2
* O(nlogn), O(n+logn), , logn
* O(n) */
/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
int i, leftn, num_elements, tmpos;
leftn = rpos - 1;
tmpos = lpos;
num_elements = rightn - lpos + 1;
/*main loop*/
while (lpos <= leftn && rpos <= rightn)
if (a[lpos] <= a[rpos])
tmp_array[tmpos++] = a[lpos++];
else
tmp_array[tmpos++] = a[rpos++];
while (lpos <= leftn) /*copy rest of the first part*/
tmp_array[tmpos++] = a[lpos++];
while (rpos <= rightn) /*copy rest of the second part*/
tmp_array[tmpos++] = a[rpos++];
/*copy array back*/
for (i = 0; i < num_elements; i++, rightn--)
a[rightn] = tmp_array[rightn];
}
void msort(int a[], int tmp_array[], int left, int right)
{
int center;
if (left < right)
{
center = (right + left) / 2;
msort(a, tmp_array, left, center);
msort(a, tmp_array, center + 1, right);
merge(a, tmp_array, left, center + 1, right);
}
}
void merge_sort(int a[], int n)
{
int *tmp_array;
tmp_array = (int *)malloc(n * sizeof(int));
if (tmp_array != NULL)
{
msort(a, tmp_array, 0, n - 1);
free(tmp_array);
}
else
printf("No space for tmp array!
");
}六、スタック並べ替えスタックは以下の性質を有する完全な二叉木である:各ノードの値はその左右の子供ノードの値より大きいか、または等しいか、大頂スタックと呼ばれる.あるいは、各ノードの値が左右の子供ノードの値以下であることを、小さなトップスタックと呼ぶ.
/* : , ；
* , */
/* . : . ,
* . ( , ), n-1
* , n . ,
*/
/* O(nlogn), , , O(n^2) */
//
#define leftChild(i) (2*(i) + 1)
void percDown(int *arr, int i, int N)
{
int tmp, child;
for (tmp = arr[i]; leftChild(i) < N; i = child)
{
child = leftChild(i);
if (child != N - 1 && arr[child + 1] > arr[child])
child++;
if (arr[child] > tmp)
arr[i] = arr[child];
else
break;
}
arr[i] = tmp;
}
void HeapSort(int *arr, int N)
{
int i;
for (i = N / 2; i >= 0; i--)
percDown(arr, i, N);
for (i = N - 1; i > 0; i--)
{
swap1(&arr[0], &arr[i]);
percDown(arr, 0, i);
}
}
int main(void)
{
int arr[] = { 9, 2, 5, 8, 3, 4, 7, 1, 6, 10};
HeapSort(arr, 10);
for (int i = 0; i < 10; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}七:カウントソート
カウントソート(Counting sort)は安定したソートアルゴリズムである.カウントソートには、追加の配列Cが使用され、i番目の要素は、ソートされる配列Aの値がiに等しい要素の数である.次に配列Cに従ってAの要素を正しい位置に並べます.
アルゴリズムの手順は次のとおりです.
カウントのための配列
C
の長さは、ソート対象配列のデータの範囲(ソート対象配列の最大値と最小値の差に1を加算)に依存し、カウントソートはデータ範囲の広い配列に対して多くの時間とメモリを必要とする
/***************** *******************************/
void CountSort(int *arr, int num)
{
int mindata = arr[0];
int maxdata = arr[0];
for (int i = 1; i < num; i++)
{
if (arr[i] > maxdata)
maxdata = arr[i];
if (arr[i] < mindata)
mindata = arr[i];
}
int size = maxdata - mindata + 1;
// 0
int *pCount = (int *)malloc(sizeof(int) * size);
memset(pCount, 0, sizeof(int)*size);
// ， 1
for (int i = 0; i < num; i++)
++pCount[arr[i]-mindata];
//
for (int i = 1; i < size; i++)
pCount[i] += pCount[i - 1]; //
int *pSort = (int *)malloc(sizeof(int) * num);
memset((char*)pSort, 0, sizeof(int) * num);
// ，
for (int i = num - 1; i >= 0; i--)
{
// 1， 1
--pCount[arr[i]-mindata];
pSort[pCount[arr[i]-mindata]] = arr[i];
}
//
for (int i = 0; i < num; i++)
arr[i] = pSort[i];
free(pCount);
free(pSort);
}
八:バケツの並べ替え
バケツソート(Bucket sort)やいわゆる箱ソートは、配列を限られた数のバケツに分けることを原理とするソートアルゴリズムです.各バケツを個別に並べ替える(別の並べ替えアルゴリズムを再使用するか、バケツの並べ替えを再帰的に継続する可能性がある)
バケツのソートは、次の手順で行います.
struct Node
{
int key_;
struct Node *next_;
Node(int key)
{
key_ = key;
next_ = NULL;
}
};
#define bucket_size 10 //
void buck_sort(int arr[], int num)
{
Node *bucket_table[bucket_size];
memset(bucket_table, 0, sizeof(bucket_table));
// , key
for (int i = 0; i < bucket_size; i++)
bucket_table[i] = new Node(0);
int maxValue = arr[0];
for (int i = 1; i < num; i++)
{
if (arr[i] > maxValue)
maxValue = arr[i];
}
for (int j = 0; j < num; j++)
{
Node *ptr = new Node(arr[j]);// key
//
// index = (value * number_of_elements) / (maxvalue + 1)
int index = (arr[j] * bucket_size) / (maxValue + 1);
Node *head = bucket_table[index];
//
if (head->key_ == 0)
{
bucket_table[index]->next_ = ptr;
(bucket_table[index]->key_)++;
}
else
{
//
while (head->next_ != NULL && head->next_->key_ <= ptr->key_)
head = head->next_;
ptr->next_ = head->next_;
head->next_ = ptr;
(bucket_table[index]->key_)++;
}
}
//
int m, n;
for (m = 0, n = 0; n < num && m < bucket_size; m++, n++)
{
Node *ptr = bucket_table[m]->next_;
while (ptr != NULL)
{
arr[n] = ptr->key_;
ptr = ptr->next_;
n++;
}
n--;
}
//
for (m = 0; m < bucket_size; m++)
{
Node *ptr = bucket_table[m];
Node *tmp = NULL;
while (ptr != NULL)
{
tmp = ptr->next_;
delete ptr;
ptr = tmp;
}
}
}九.ベースソート
基数ソート(英語:Radix sort)は、整数をビット数で異なる数字に切断し、各ビット数でそれぞれ比較することを原理とする非比較型整数ソートアルゴリズムである.整数は文字列(名前や日付など)や特定のフォーマットの浮動小数点数も表すことができるため、基数ソートは整数にのみ使用できるわけではありません.
これは、比較対象のすべての数値(正の整数)を同じ数桁の長さに統一し、数桁の短い数の前にゼロを補うことによって実現される.そして,最下位から順に1回ソートする.これにより、最下位のソートから最上位のソートが完了するまで、数列は秩序化されたシーケンスになります.
基数ソート方式はLSD(Least significant digital)またはMSD(Most significant digital)を用いることができ、LSDのソート方式はキー値の右端から始まり、MSDは逆にキー値の左端から始まる.
void base_sort_ISD(int *arr, int num)
{
Node *buck[10]; //
Node *tail[10]; // ，
// buck
int i, MaxValue, kth, high, low;
Node *ptr;
for(MaxValue = arr[0], i = 1; i < num; i++)
MaxValue = max(MaxValue, arr[i]);
memset(buck, 0, sizeof(buck));
memset(tail, 0, sizeof(buck));
for(low = 1; high = low * 10, low < MaxValue; low *= 10)
{
//
for(i = 0; i < num; i++)
{
//
kth = (arr[i] % high) / low;// ，
ptr = new Node(arr[i]); //
//
if (buck[kth] != NULL)
{
tail[kth]->next_ = ptr;
tail[kth] = ptr;
}
else
{
buck[kth] = ptr;
tail[kth] = ptr;
}
}
// （ ）
for (kth = 0, i = 0; kth < num; i++)
{
while (buck[i] != NULL)
{
arr[kth++] = buck[i]->key_;
ptr = buck[i];
buck[i] = buck[i]->next_;
delete ptr;
}
}
memset(tail, 0, sizeof(buck));
}
}十.クイックソート
ソートする配列をA[0]......A[N-1]とし、まず任意に1つのデータ(通常は配列の最初の数)をキーデータとして選択し、それより小さい数をすべて前に置き、それより大きい数をすべて後ろに置くプロセスを高速ソートと呼ぶ.なお、高速ソートは安定したソートアルゴリズムではなく、すなわち、複数の同じ値の相対位置がアルゴリズムの終了時に変動する可能性がある.
void QuickSort(int a[],int numsize)/*a ，numsize */
{
int i=0,j=numsize-1;
int val=a[0];/* val */
if(numsize>1)/* 2， */
{
while(ii;j--)
if(a[j]val)
{
a[j--]=a[i];
break;
}
}
a[i]=val;/* val a[i] */
QuickSort(a,i);/* ， i */
QuickSort(a+i+1,numsize-i-1);/* i+2 numsize numsize-1-i */
}
} 原文住所:住所