最も完全なソートアルゴリズムの原理とコードの実現
ソートアルゴリズムの実装プロセス
序言:最近各种のソートアルゴリズムを复习して、面接がソートアルゴリズムに対して试験するのが比较的に频繁で、しかもブラシの过程の中で各种のソートテーマに出会って、しかし往々にしてすべて万変してその宗を离れないで、そのため、専门的に各种のソートアルゴリズムとその実现方法を総括して、C言语でその基本原理を実现しました.本明細書で説明するアルゴリズムは、主に次のとおりです.バブルソート 選択ソート 挿入ソート ヒルソート 集計ソート クイックソート クイック選択 スタックソート 1.泡立ちソート
手順を実行します.は隣接する2つの要素を比較し、前の要素が後の要素より大きい場合、2つの要素を置き換えます.順次類推し,隣接する各ペアの要素に対して同じ操作を行い,配列の末尾に最大の要素を格納することができる. は、すべての要素について最初のステップの操作を繰り返し、最後の要素のセットが比較されるまで除去し、配列を小さいものから大きいものに並べることができる.
2.ソートの選択
手順を実行します.既知のシーケンスで最小(大)の要素を探し、開始位置に配置します. 残りのデータから最小(大)要素を探し、2番目の位置に配置します. すべての要素が配列されるまで、上記の2つのステップを繰り返します.
3.ソートの挿入
手順を実行します.は、最初の要素をソートされた要素として取り出します. は、次の要素を取り出し、ソートされた要素の中で後から前へ遍歴する. 現在の要素が新しい要素より大きい場合、新しい要素は前の要素と比較されます. は、新しい要素よりも小さな要素または等しい要素が見つかるまで、ステップ3を繰り返します. 新しい要素を現在の要素の次のビットに挿入します. で2～5ステップを繰り返します.
4.ヒルソート
手順を実行します.は、固定ステップ長を決定し、元のシーケンスを数個の等長のサブシーケンスに分割する. は、サブシーケンスを挿入ソートする. はステップを短縮し、ステップが1になるまで2つのステップを繰り返します.
5.集計ソート
アルゴリズムの手順:は、統合されたシーケンスを格納するために使用される2つの並べ替えられたシーケンスの和の大きさを有する空間を申請する. は、2つのポインタを設定し、最初の位置はそれぞれ2つの並べ替えられたシーケンスの開始位置である. は、2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ空間に入れ、ポインタを次の位置に移動する. あるポインタがシーケンスの最後に達するまで、ステップ3を繰り返す. は、別のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーします.
ソート実行手順:は、1つのシーケンスを2つのサブシーケンスに分割する. は、2つのサブシーケンスを再帰的に集計する. は、2つのサブシーケンスを1つの秩序化されたシーケンスに結合する.
6.クイックソート
手順を実行します.シーケンスから基準量を定義し、一般的にシーケンスの最初の要素を基準量として選択します. データム値を保存し、2つのポインタがそれぞれ最初の要素と最後の要素を指すように定義します. は遍歴を開始し、シーケンス内の基準値より小さい要素を前に、基準値より大きい要素をシーケンスの後ろに配置します. 基準要素を2つのポインタが等しいところに挿入します(境界条件に注意). 再帰的にステップ1−3を行い、二重ポインタが交換されていない場合、並べ替えられた配列を得ることができる.
6.1快速選択
実行方法:
高速選択は、高速ソートに基づく変種アルゴリズムであり、ソートアルゴリズムではなく、検索シーケンスの最大(最小)K番目の数によく用いられる検索アルゴリズムである.
基本原理は高速ソートと同様に、まず基準値を探して、それから大きいものを後ろに置いて、小さいものを前に置いて、異なるところは、高速選択は二重再帰を必要としないことです.彼はソートを必要としないので、エッジに入って再帰検索を行うだけです.
高速選択と高速ソートの原理は基本的に一致しているが,ここでは2つの異なる遍歴法を用いて実現し,上記では賦値法を用い,今回は交換法を用いた.どちらの方法でもPartition関数を実現できるが,境界条件は異なる.長い間境界条件の問題を考えていたので、ここに記録します.
この方法は、ベース準値より大きい(小さい)最初の数aを見つけたとき、すぐに最初の数に値を付与する補助交換関数を定義する必要がある.このとき、最初の数は基準値であり、base変数に保存されているため、配列の最初の要素は実際には不要な要素であるため、直接値を付与することができる.付与後、aはその役に立たない数値になった.
高速選択で使用する方法は、基準値より1番目に大きい値を検索した後、基準値より1番目に小さい値を検索し、2つの位置を決定した後、交換操作を行い、2つのポインタを移動することです.この場合、境界条件はleft<=rightとする必要があります.この検索方法では基準値start==0を保存する必要がないため、leftポインタはleft+1を指し、ソート対象配列arrに2つの数しかない場合、left==rightの場合、境界条件がleft
7.ヒープソート
大きいルートヒープ:すべての親ノードの値が子ノードより大きい
最小ヒープ:すべての親ノードの値が子ノードより小さい
プロセスの実行:は初期スタックを構築し、無秩序シーケンスを1つの大きなスタックまたは最小スタック(一般的に、大きなスタックは大きなものから小さいものへ、最小スタックは小さいものから大きいものへの配列)に構築する. は、最後の要素が最大(最小)になるように、スタックトップ要素を最後の要素と交換し、分離する. 残りの要素をさらに大きなスタック(最小スタック)を構築し、上記の手順を繰り返して配列されたシーケンスを得る.
序言:最近各种のソートアルゴリズムを复习して、面接がソートアルゴリズムに対して试験するのが比较的に频繁で、しかもブラシの过程の中で各种のソートテーマに出会って、しかし往々にしてすべて万変してその宗を离れないで、そのため、専门的に各种のソートアルゴリズムとその実现方法を総括して、C言语でその基本原理を実现しました.本明細書で説明するアルゴリズムは、主に次のとおりです.
手順を実行します.
/**
*
* ---- O(n)
* ---- O(n^2)
* ---- O(n^2)
* ---- O(1)
* -----------
**/
void BubbleSort(int* arr, int len) {
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
2.ソートの選択
手順を実行します.
/**
*
* ---- O(n^2)
* ---- O(n^2)
* ---- O(n^2)
* ---- O(1)
* -----------
**/
void SelecttionSort(int* arr, int len) {
for (int i = 0; i < len; i++) {
int index = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
if (index == i) {
continue;
}
else {
int tmp = arr[index];
arr[index] = arr[i];
arr[i] = tmp;
}
}
}
3.ソートの挿入
手順を実行します.
/**
*
* ---- O(n)
* ---- O(n^2)
* ---- O(n^2)
* ---- O(1)
* -----------
**/
void InsertSort(int* arr, int len) {
int i, j;
int target;
for (i = 1; i < len; i++) {
target = arr[i];
for (j = i; j > 0 && arr[j - 1] > target; j--) {
arr[j] = arr[j - 1];
}
arr[j] = target;
}
}
4.ヒルソート
手順を実行します.
/**
* ----
* ---- O(nlogn)
* ---- O(nlogn)
* ------ O(1)
* -----------
**/
void ShellSort(int* arr, int len) {
int i, j, k, increasement;
int tmp;
for (increasement = len / 2; increasement > 0; increasement /= 2) {
for (i = 0; i < increasement; i++) {
for (j = i + increasement; j < len; j += increasement) {
if (arr[j] < arr[j - increasement]) {
tmp = arr[j];
for (k = j - increasement; k >= 0 && arr[k] > tmp; k -= increasement) {
arr[k + increasement] = arr[k];
}
arr[k + increasement] = tmp;
}
}
}
}
}
int main() {
int a[10] = {
8, 2, 1, 5, 9, 7, 4, 6, 3, 0};
ShellSort(a, 10);
for (int i = 0; i < 10; i++) {
printf("%d
", a[i]);
}
return 0;
}
5.集計ソート
アルゴリズムの手順:
ソート実行手順:
/**
* ---- O(nlogn)
* ---- O(nlogn)
* ---- O(nlogn)
* ------ O(n)
* -----------
**/
void Merge(int* arr, int* tmp, int start, int mid, int end) {
//
int length = 0; //
int i_start = start; //
int i_end = mid; //
int j_start = mid + 1; //
int j_end = end; //
while (i_start <= i_end && j_start <= j_end) {
// TMP
if (arr[i_start] < arr[j_start]) {
tmp[length++] = arr[i_start];
i_start++;
}
else {
tmp[length++] = arr[j_start];
j_start++;
}
}
while (i_start <= i_end) {
tmp[length++] = arr[i_start++];
}
while (j_start <= j_end) {
tmp[length++] = arr[j_start++];
}
for (int i = 0; i < length; i++) {
// tmp arr
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int start, int end, int* tmp) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
MergeSort(arr, start, mid, tmp);
MergeSort(arr, mid + 1, end, tmp);
Merge(arr, tmp, start, mid, end, tmp);
}
int main() {
//
int a[8] = {
5, 2, 3, 6, 1, 0, 7, 4};
int b[8] = {
0};
Merge(a, 0, 7, b);
for (int i = 0; i < 8; i++) {
printf("%d
", a[i]);
}
return 0;
}
6.クイックソート
手順を実行します.
/**
* ---- O(nlogn)
* ---- O(n^2)
* ---- O(nlogn)
* ------ O(logn)
* -----------
* base ， arr[right] （
* ）， left+1， right ， ， left right。 * ， left == right 。
* ， left < right， left == right ， （ ） * （ ）， ， left++（right++） ， （ ） ， * left == right ， ， ， 。
** ， 。
**/
int Partition(int* arr, int len, int start, int end) {
if (len <= 0 || arr == NULL || start < 0 || end >= len || end <= 0) {
return -1;
}
int base = arr[start]; //
int left = start; //
int right = end;
while (left < right) {
// ， left == right
while (left < right && arr[right] >= base) {
// ，
right--;
}
if (left < right) {
// ，
arr[left] = arr[right];
left++;
}
while (left < right && arr[left] < base) {
left++;
}
if (left < right) {
arr[right] = arr[left];
right--;
}
}
arr[left] = base;
return left;
}
void QuickSort(int* arr, int len, int start, int end) {
if (start == end) {
// ，
return;
}
int index = Partition(arr, len, start, end);
if (index > start) {
QuickSort(arr, len, start, index - 1); //
}
if (index < end) {
QuickSort(arr, len, index + 1, end); //
}
}
int main() {
int arr[10] = {
8, 2, 1, 5, 9, 7, 4, 6, 3, 0};
QuickSort(arr, 10, 0, 9);
for (int i = 0; i < 10; i++) {
printf("%d
", arr[i]);
}
return 0;
}
6.1快速選択
実行方法:
高速選択は、高速ソートに基づく変種アルゴリズムであり、ソートアルゴリズムではなく、検索シーケンスの最大(最小)K番目の数によく用いられる検索アルゴリズムである.
基本原理は高速ソートと同様に、まず基準値を探して、それから大きいものを後ろに置いて、小さいものを前に置いて、異なるところは、高速選択は二重再帰を必要としないことです.彼はソートを必要としないので、エッジに入って再帰検索を行うだけです.
高速選択と高速ソートの原理は基本的に一致しているが,ここでは2つの異なる遍歴法を用いて実現し,上記では賦値法を用い,今回は交換法を用いた.どちらの方法でもPartition関数を実現できるが,境界条件は異なる.長い間境界条件の問題を考えていたので、ここに記録します.
この方法は、ベース準値より大きい(小さい)最初の数aを見つけたとき、すぐに最初の数に値を付与する補助交換関数を定義する必要がある.このとき、最初の数は基準値であり、base変数に保存されているため、配列の最初の要素は実際には不要な要素であるため、直接値を付与することができる.付与後、aはその役に立たない数値になった.
高速選択で使用する方法は、基準値より1番目に大きい値を検索した後、基準値より1番目に小さい値を検索し、2つの位置を決定した後、交換操作を行い、2つのポインタを移動することです.この場合、境界条件はleft<=rightとする必要があります.この検索方法では基準値start==0を保存する必要がないため、leftポインタはleft+1を指し、ソート対象配列arrに2つの数しかない場合、left==rightの場合、境界条件がleft
/**
* ---- O(n)
* ---- O(n^2)
* ---- O(n)
* ------ O(logn)
* ----------- /
**/
void swap(int* arr, int a, int b) {
int tmp;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
int Partition(int* arr, int len, int start, int end) {
int left = start + 1;
int right = end;
while (left <= right) {
while (left <= right && arr[right] > arr[start]) {
right--;
}
while (left <= right && arr[left] < arr[start]) {
left++;
}
if (left <= right) {
swap(arr, left++, right--);
}
}
swap(arr, start, right);
return right;
}
int findKthLargest(int* nums, int numsSize, int k) {
if (nums == NULL || numsSize == 0) {
return 0;
}
int start = 0;
int end = numsSize - 1;
while (1) {
int position = Partition(arr, numsSize, start, end);
if (position > k - 1) {
end = position - 1;
}
else if (position == k - 1) {
return nums[position];
}
else {
start = position + 1;
}
}
}
7.ヒープソート
大きいルートヒープ:すべての親ノードの値が子ノードより大きい
最小ヒープ:すべての親ノードの値が子ノードより小さい
プロセスの実行:
/**
（leetocode 《 K 》）
* ---- O(nlogn)
* ---- O(nlogn)
* ---- O(nlogn)
* ------ O(1)
* -----------
**/
void swap(int* arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
int heapify(int* arr, int i, int len) {
int lc = 2 * i + 1; //
int lr = 2 * i + 2; //
int max = i; //
if (lc < len && arr[lc] > arr[max]) {
max = lc；
}
if (lr < len && arr[lr] > arr[max]) {
max = lr;
}
if (max != i) {
//
swap(arr, max, i);
heapify(arr, max, len); // ，
}
}
void buildheap(int arr, int len) {
int last_node = len - 1;
int parent = (last_node - 1) / 2;
int i;
for (i = parent; i >= 0; i--) {
heapify(arr, i, len);
}
}
void heapSort(int arr, int len) {
buildheap(arr, len);
int i;
for (i = len - 1; i >= 0; i--) {
swap(arr, i, 0); // ，
heapify(arr, 0, i); //
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) {
heapSort(arr, arrSize);
* returnSize = k;
int* nums = (int*)malloc(sizeof(int) * k);
int i;
for (i = 0; i < k; i++) {
nums[i] = arr[i];
}
return nums;
}