各種排序算法復雜度比較
冒泡排序
兩兩比較，從底往上升蔓钟。
算法原理
由最后一位開始，相鄰兩數(shù)兩兩比較佣谐，小的往上升狭魂，這樣一趟下來，最小的數(shù)就被排在了第一位镐牺，第二趟也是如此睬涧，如此類推痹束，直到所有的數(shù)據(jù)排序完成c++代碼實現(xiàn)
void bubble_sort(int arr[], int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = len - 1; j > i; j--)
{
if (arr[j] < arr[j - 1])
{
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
選擇排序
固定位置祷嘶，找元素
- 算法原理
- 先在未排序序列中找到最小（大）元素嘉汰，存放到排序序列的起始位置
- 再從剩余未排序元素中繼續(xù)尋找最小（大）元素接箫，然后放到已排序序列的末尾辛友。
- 以此類推废累，直到所有元素均排序完畢邑滨。
- c++代碼實現(xiàn)
void select_sort(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)
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
插入排序
固定元素找位置
- 算法原理
將數(shù)據(jù)分為兩部分，有序部分與無序部分，一開始有序部分包含第1個元素归榕，依次將無序的元素插入到有序部分刹泄，直到所有元素有序级乐。插入排序又分為直接插入排序、二分插入排序乞旦、鏈表插入等，這里只討論直接插入排序玖姑。它是穩(wěn)定的排序算法，時間復雜度為O(n^2) - c++代碼實現(xiàn)
void insert_sort(int arr[], int len)
{
for (int i = 1; i < len; i ++)
{
int j = i - 1;
int k = arr[i];
while (j > -1 && k < arr[j] )
{
arr[j + 1] = arr[j];
j --;
}
arr[j + 1] = k;
}
}
快速排序
挖坑填數(shù)+分治法
- 算法原理
- 選擇一個基準元素闪彼，第一個或最后一個
- 通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分比基準小描馅，另外一部分比基準大
- 此時基準已經(jīng)在其排好序后的位置
- 然后再分別對這兩部分數(shù)據(jù)用同樣的方法進行排序铭污，整個排序過程可以遞歸進行，直到整個數(shù)據(jù)變成有序序列刁绒。
總結
1．i =L; j = R; 將基準數(shù)挖出形成第一個坑a[i]傻盟。
2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中诽表。
3．i++由前向后找比它大的數(shù)竿奏，找到后也挖出此數(shù)填到前一個坑a[j]中。
4．再重復執(zhí)行2候址，3二步，直到i==j赔蒲，將基準數(shù)填入a[i]中。
- c++代碼實現(xiàn)
void quick_sort(int arr[], int left, int right)
{
if (left < right)
{
int i = left, j = right, target = arr[left];
while (i < j)
{
while (i < j && arr[j] > target)
j--;
if (i < j)
arr[i++] = arr[j];
while (i < j && arr[i] < target)
i++;
if (i < j)
arr[j] = arr[i];
}
arr[i] = target;
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
歸并排序
算法原理
假設序列共有n個元素：
將序列每相鄰兩個數(shù)字進行歸并操作（merge)，形成floor(n/2)個序列，排序后每個序列包含兩個元素
將上述序列再次歸并返帕，形成floor(n/4)個序列荆萤，每個序列包含四個元素
重復步驟2，直到所有元素排序完畢c++代碼實現(xiàn)
void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
{
int first = start_index, second = mid_index + 1;
int index = 0;
//比較二個數(shù)列的第一個數(shù)，誰小就先取誰殖蚕，取了后就在對應數(shù)列中刪除這個數(shù),然后再進行比較，直到有數(shù)列為空，
while (first < mid_index + 1 && second < end_index + 1)
{
if (arr[first] > arr[second])
temp_arr[index ++] = arr[second ++];
else
temp_arr[index ++] = arr[first ++];
}
//將另一個數(shù)列的數(shù)據(jù)依次取出即可
while (first < mid_index + 1)
{
temp_arr[index ++] = arr[first ++];
}
while (second < end_index + 1)
temp_arr[index ++] = arr[second ++];
for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
arr[j] = temp_arr[i];
}
void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
{
if (start_index < end_index)
{
int mid_index = (start_index + end_index) / 2;
merge_sort(arr, temp_arr, start_index, mid_index);
merge_sort(arr, temp_arr, mid_index + 1, end_index);
merge(arr, temp_arr, start_index, mid_index, end_index);
}
}
堆排序
- 算法原理（以最大堆為例）
- 構建大頂堆
- 初始化堆
- 從最后一個非葉節(jié)點開始調整
- 每次調節(jié)都從父左右節(jié)點中選最大的同父節(jié)點交換
- 交換之后可能導致被交換的孩子節(jié)點不滿足堆的性質进宝，需要重新調整
- 將堆頂元素通過最后一個元素 R[n] 交換
- 由于交換后新堆頂可能違反堆的性質党晋，因此需要重新調整為新堆，然后再次將 R[1]與無序區(qū)最后一個元素交換
- 構建大頂堆
- 不斷重復，直到有序區(qū)的個數(shù)為n－1
- c++代碼實現(xiàn)
/**
* 將數(shù)組arr構建大根堆
* @param arr 待調整的數(shù)組
* @param i 待調整的數(shù)組元素的下標
* @param len 數(shù)組的長度
*/
void heap_adjust(int arr[], int i, int len)
{
int child;
int temp;
for (; 2 * i + 1 < len; i = child)
{
child = 2 * i + 1; // 子結點的位置 = 2 * 父結點的位置 + 1
// 得到子結點中鍵值較大的結點
if (child < len - 1 && arr[child + 1] > arr[child])
child ++;
// 如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點
if (arr[i] < arr[child])
{
temp = arr[i];
arr[i] = arr[child];
arr[child] = temp;
}
else
break;
}
}
/**
* 堆排序算法
*/
void heap_sort(int arr[], int len)
{
int i;
// 調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素
for (int i = len / 2 - 1; i >= 0; i--)
{
heap_adjust(arr, i, len);
}
for (i = len - 1; i > 0; i--)
{
// 將第1個元素與當前最后一個元素交換辟狈，保證當前的最后一個位置的元素都是現(xiàn)在的這個序列中最大的
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值
heap_adjust(arr, 0, i);
}
}
希爾排序
分組插入排序亚隅，又稱縮小增量排序
- 算法原理
- 將整個待排元素分割成若干個序列（由相鄰某個增量的元素組成）
- 將這些序列分別進行直接插入排序
- 縮減增量，再重復上述步驟
- 待元素基本有序（增量足夠小時）在對全體元素進行一次直接插排
- c++代碼實現(xiàn)
void shellsort3(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}
基數(shù)排序
- 算法原理
- 首先根據(jù)個位數(shù)的數(shù)值，在走訪數(shù)值時將它們分配至編號0到9的桶子中
- 接下來將這些桶子中的數(shù)值重新串接起來酿联，成為新的數(shù)列
- 根據(jù)十位數(shù)數(shù)值來分配贞让，重復上述步驟
- 續(xù)進行以上的動作直至最高位數(shù)為止
- c++代碼實現(xiàn)
//最大位數(shù)
int maxbit(int data[], int n)
{
int d = 1; //保存最大的位數(shù)
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
![Uploading 273973-19cf4a1e58b6ebaf_927583.png . . .]
p *= 10;
++d;
}
}
return d;
}
//基數(shù)排序
void radixsort(int data[], int n)
{
int d = maxbit(data, n);
int tmp[n];
int count[10]; //計數(shù)器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //進行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計數(shù)器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //統(tǒng)計每個桶中的記錄數(shù)
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //將臨時數(shù)組的內(nèi)容復制到data中
data[j] = tmp[j];
radix = radix * 10;
}
}
計數(shù)排序
- 算法原理
- 遍歷一遍整個數(shù)組，找出數(shù)組中最大數(shù)和最小數(shù)之間的差距 range,然后開辟一個大小為range的數(shù)組count并全部初始化為0；
- 再次遍歷整個數(shù)組江咳，把每個元素的值映射到count的下標index(val –> (val-min))甥雕，每映射到一個index挟阻，就把count[index]加一脱拼；
- 根據(jù)統(tǒng)計結果count，把數(shù)寫會原數(shù)組，某個值index要寫count[index]遍到原數(shù)組娃惯，這樣馒稍，原數(shù)組就有序了
- c++代碼實現(xiàn)
void CountSort(int *arr, int len)
{
assert(arr);
if(len <= 1)
return ;
int max = arr[0];
int min = arr[0];
//統(tǒng)計數(shù)組中的最大值和最小值
for(int i = 0; i < len; ++i)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
int range = max + 1 - min; //得到最大最小值的差距
int *count = new int[range]; //用于記錄數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)
for(int i = 0; i < len; ++i) // 初始化
count[i] = 0;
for(int i = 0; i < len; ++i)
count[ arr[i]-min ]++; //arr[i] - min 映射到tmp中的一個下標，該下標下的值是這個數(shù)出現(xiàn)的次數(shù)
int index = 0;
for(int i = 0; i < range; ++i) //再把臨時數(shù)組記錄的數(shù)分別拷貝到原數(shù)組中
{
while(count[i]--) //每個下標下拷貝對應的次數(shù)
arr[index++] = i + min;
}
}
