排序
比較
分類
-
比較排序的時間復雜度的下界O(nlogn)
對于n個待排序元素，在未比較時，可能的正確結果有n!種，在經過一次比較后，其中兩個元素的順序被確定，所以可能的正確結果剩余n!/2種（確定之前兩個元素的前后位置的情況是相同，確定之后相當于少了一半的可能性），依次類推，直到經過m次比較，剩余可能性n!/(2m)種，直到n!/(2m)<=1時，結果只剩余一種，根據斯特靈公式，此時的比較次數m為o(nlogn)次，所以基于排序的比較演算法，最優情況下，復雜度是O(nlogn)的，
原始碼
- Sort.cpp
/**
* @file Sort.cpp
* @author Sprinining ([email protected])
* @brief 交換排序：冒泡排序、快速排序
* 選擇排序：普通選擇排序、堆排序
* 插入排序：直接插入排序、二分插入排序、希爾排序
* 歸并排序：普通歸并排序
* 分布排序：計數排序、桶排序、基數排序
* @version 0.1
* @date 2022-05-06
*
* @copyright Copyright (c) 2022
*
*/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b) { return *(int*)(a) - *(int*)b; }
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// a, b不能是同一個地址的東西，否則會把該地址清零
void swap2(int* a, int* b) {
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
void display(int* ary, int size) {
for (int i = 0; i < size; i++) {
printf("%d ", ary[i]);
}
puts("");
}
// 1.冒泡排序
void bubbleSort(int* array, int size) {
// 比較size-1輪
for (int i = 0; i < size - 1; i++) {
// 是否已經有序了
bool isSorted = true;
// 每一輪都會有個大元素移到后面
for (int j = 0; j < size - 1 - i; j++) {
// 將相鄰的兩個比較，大的移到后面
if (array[j] > array[j + 1]) {
// 有交換的說明沒排好
isSorted = false;
swap(&array[j], &array[j + 1]);
}
}
if (isSorted == true) break;
}
display(array, size);
}
void quickSortRecursive(int* array, int left, int right) {
if (left >= right) return;
int i = left;
int j = right;
// 基準元素
int key = array[left];
// 分成兩半，左邊小于基準元素，右邊大于基準元素
while (i < j) {
// 從右往左找第一個小于key的
while (i < j && array[j] >= key) {
j--;
}
// 與key交換
if (i < j) {
array[i] = array[j];
// array[j]不用立刻放入key，后面可能會有比key大的元素防止這
i++;
}
// 從左往右找第一個大于key的
while (i < j && array[i] <= key) {
i++;
}
// 與key交換
if (i < j) {
array[j] = array[i];
j--;
}
}
// 回圈退出時i=j
array[i] = key;
quickSortRecursive(array, left, i - 1);
quickSortRecursive(array, i + 1, right);
}
// 2.快速排序
void quickSort(int* array, int size) {
quickSortRecursive(array, 0, size - 1);
display(array, size);
}
// 3.普通選擇排序
void selectionSort(int* array, int size) {
// size-1輪
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
// 從后面找更小的
for (int j = i + 1; j < size; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 確實有更小的
if (minIndex != i) {
swap(&array[i], &array[minIndex]);
}
}
display(array, size);
}
// 自頂向下調整堆頂（只有堆頂不符合堆的定義）
void adjustHeap(int* array, int currentIndex, int size) {
int temp = array[currentIndex];
int leftChildIndex = 2 * currentIndex + 1;
while (leftChildIndex <= (size - 1)) {
// 找更大點的子節點
if (leftChildIndex < (size - 1) &&
array[leftChildIndex] < array[leftChildIndex + 1]) {
leftChildIndex++;
}
if (array[leftChildIndex] <= temp) break;
// 與子節點交換
array[currentIndex] = array[leftChildIndex];
currentIndex = leftChildIndex;
leftChildIndex = 2 * currentIndex + 1;
}
array[currentIndex] = temp;
}
// 4.堆排序
void heapSort(int* array, int size) {
// 從第一個非葉子節點開始，自底向上
for (int i = (size - 2) / 2; i >= 0; i--) {
adjustHeap(array, i, size);
}
printf("建堆：");
display(array, size);
// size-1輪
for (int i = 1; i < size; i++) {
swap(&array[0], &array[size - i]);
// 已經是堆了，在修改完堆頂后只需要對堆頂進行重定位
adjustHeap(array, 0, size - i);
}
display(array, size);
}
// 5.直接插入排序
void insertionSort(int* array, int size) {
// size-1輪
// [0, i-1]是有序序列
for (int i = 1; i < size; i++) {
// 待插入的元素
int temp = array[i];
// 插入已經有序的序列
// 從有序序列的末尾往前找第一個小于等于temp的
int j = i - 1;
while (j >= 0 && (array[j] > temp)) {
// 邊找邊把不符合的元素后移
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
display(array, size);
}
// 6.二分插入排序
void binaryInsertionSort(int* array, int size) {
for (int i = 1; i < size; i++) {
int temp = array[i];
// 二分查找插入位置
int left = 0;
int right = i - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (array[mid] >= temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 回圈結束后left就是應該插入的下標
// 把下標從left到i-1的都往后移動一位
for (int j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = temp;
}
display(array, size);
}
// 7.希爾排序
void shellSort(int* array, int size) {
// 步長（讓一個元素可以一次性地朝最終位置前進一大步）
int gap = size / 2;
while (gap > 0) {
// 間隔gap的分在同一組(共gap組，gap下標[0,
// gap-1]是這gap組每組的首個已排序元素)，進行普通的插入排序
for (int i = gap; i < size; i++) {
int temp = array[i];
int j = i - gap;
while (j >= 0 && array[j] > temp) {
array[j + gap] = array[j];
j -= gap;
}
array[j + gap] = temp;
}
printf("gap:%d\n", gap);
display(array, size);
gap = gap / 2;
}
}
// 分治-治
void mergeSort_conquer(int* array, int left, int mid, int right, int* temp) {
// [left, mid]和[mid+1, right]兩個有序陣列
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (array[i] < array[j]) {
temp[index++] = array[i++];
} else {
temp[index++] = array[j++];
}
}
// 剩余元素直接放入temp
while (i <= mid) {
temp[index++] = array[i++];
}
while (j <= right) {
temp[index++] = array[j++];
}
// 放回原陣列
index = 0;
while (left <= right) {
array[left++] = temp[index++];
}
}
// 分治-分
void mergeSort_divide(int* array, int left, int right, int* temp) {
if (left >= right) return;
int mid = left + (right - left) / 2;
// 左邊歸并排序
mergeSort_divide(array, left, mid, temp);
// 右邊歸并排序
mergeSort_divide(array, mid + 1, right, temp);
// 合并兩個有序序列
mergeSort_conquer(array, left, mid, right, temp);
}
// 8.普通歸并排序
void mergeSort(int* array, int size) {
int* temp = (int*)malloc(sizeof(int) * size);
mergeSort_divide(array, 0, size - 1, temp);
display(array, size);
}
// TODO: 迭代版歸并排序
// 9.計數排序(每個桶只存盤單一鍵值) 0~10
void countingSort(int* array, int size) {
int* frequency = (int*)calloc(11, sizeof(int));
// frequency[i]表示統計i出現的次數
for (int i = 0; i < size; i++) {
frequency[array[i]]++;
}
display(frequency, 11);
// frequency[i]表示小于等于i的個數
for (int i = 1; i < 11; i++) {
frequency[i] += frequency[i - 1];
}
display(frequency, 11);
int* sorted = (int*)calloc(size, sizeof(int));
// 倒著遍歷原陣列，把原陣列放在新陣列正確的位置上
for (int i = size - 1; i >= 0; i--) {
// 有frequency[array[i]]個小于等于array[i]個元素
// 說明array[i]排在第frequency[array[i]]個位置，下標就是frequency[array[i]]-1
// 放好后frequency[array[i]]要自減
sorted[--frequency[array[i]]] = array[i];
printf("frequency:\t");
display(frequency, 11);
printf("sorted:\t\t");
display(sorted, size);
}
}
typedef struct {
int** bucket;
int row;
int column;
int* index;
} Bucket;
// 10.桶排序(每個桶存盤一定范圍的數值)
// 數要相對均勻分布，桶的個數也要合理設計(需要知道輸入資料的上界和下界和分布情況)，桶排序是一種用空間換取時間的排序
void bucketSort(int* array, int size) {
Bucket* b = (Bucket*)malloc(sizeof(Bucket));
b->row = 5;
b->column = 3;
b->index = (int*)calloc(b->row, sizeof(int));
b->bucket = (int**)malloc(sizeof(int) * b->row);
for (int i = 0; i < b->row; i++) {
b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
}
// 放入桶
for (int i = 0; i < size; i++) {
int index = array[i] / 10;
b->bucket[index][b->index[index]++] = array[i];
}
size = 0;
// 對每個桶進行排序（可用其他演算法）
for (int i = 0; i < b->row; i++) {
qsort(b->bucket[i], b->column, sizeof(int), cmp);
for (int j = 0; j < b->column; j++) {
array[size++] = b->bucket[i][j];
}
}
display(array, size);
}
// 11.基數排序(根據鍵值的每位數字來分配桶)
void radixSort(int* array, int size) {
Bucket* b = (Bucket*)malloc(sizeof(Bucket));
b->row = 10;
b->column = 10;
b->index = (int*)calloc(b->row, sizeof(int));
// 臨時存放按某一位排好序的序列
b->bucket = (int**)malloc(sizeof(int) * b->row);
for (int i = 0; i < b->row; i++) {
b->bucket[i] = (int*)malloc(sizeof(int) * b->column);
}
// 最大的數的位數為3
for (int i = 0; i < 3; i++) {
// 按某一位重新排序
for (int j = 0; j < size; j++) {
int index = (array[j] / (int)pow(10, i)) % 10;
b->bucket[index][b->index[index]++] = array[j];
}
// 放回原陣列
int returnSize = 0;
for (int j = 0; j < b->row; j++) {
for (int k = 0; k < b->index[j]; k++) {
array[returnSize++] = b->bucket[j][k];
}
// 重置下標陣列
b->index[j] = 0;
}
}
display(array, size);
}
void testSort() {
// int a[] = {1, 0, 7, 2, 10, 5, 2, 8, 6, 0};
// display(a, 10);
// bubbleSort(a, 10);
// quickSort(a, 10);
// selectionSort(a, 10);
// heapSort(a, 10);
// insertionSort(a, 10);
// binaryInsertionSort(a, 10);
// shellSort(a, 10);
// mergeSort(a, 10);
// countingSort(a, 10);
// int b[] = {1, 8, 7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24};
// display(b, 15);
// bucketSort(b, 15);
int c[] = {53, 3, 542, 748, 14, 77, 214, 154, 63, 616};
radixSort(c, 10);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/469804.html
標籤：其他