目錄
一，計數(shù)排序
1，基本思想
2，思路實現(xiàn)
3，計數(shù)排序的特性總結(jié)：
二，排序算法復(fù)雜度及穩(wěn)定性分析
三，排序系列所有源代碼
Sort.h
Sort.c
Stack.h
Stack.c
一，計數(shù)排序
計數(shù)排序也叫非比較排序；
1，基本思想
計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用
操作步驟：
1，統(tǒng)計相同元素出現(xiàn)次數(shù)
2，根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
圖解原理：
對這樣一個不需要比較的排序就完成了；
2，思路實現(xiàn)
// 計數(shù)排序
void CountSort(int* arr, int n)
{
int i = 0;
int max = arr[0], min = arr[0];
//找最大，最小值
for (i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//空間大小
int sum = max - min + 1;
//開辟空間并且使元素值都為0
int* arr1 = (int*)calloc(sum, sizeof(int));
//給新數(shù)組賦值
for (i = 0; i < n; i++)
{
arr1[arr[i] - min]++;
}
int j = 0;
//回收到原來的序列中
for (i = 0; i < sum; i++)
{
while (arr1[i]--)
{
arr[j++] = i + min;
}
}
}然后我們運行測試一下：
可以看到是有序的，選擇排序就?OK?了；
3，計數(shù)排序的特性總結(jié)：
1，?計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限
2.，時間復(fù)雜度：O(N+K)
3，?空間復(fù)雜度：O(N)
4,?穩(wěn)定性：穩(wěn)定
二，排序算法復(fù)雜度及穩(wěn)定性分析
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
| 冒泡排序 | O(N^2) | O(N) | O(N^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(N^2)? ?? | O(N^2)? | O(N^2)? | O(1) | 不穩(wěn)定 |
| 直接插入排序 | O(N^2)? | O(N) | O(N^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(NlongN)~O(N^2) | O(N^1.3) | O(N^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(NlongN) | O(NlongN) | O(NlongN) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(NlongN) | O(NlongN) | O(NlongN) | O(N) | 穩(wěn)定 |
| 快速排序 | O(NlongN) | O(NlongN) | O(N^2) | O(N) | 不穩(wěn)定 |
| 計數(shù)排序 | O(N+K) | O(N+K) | O(N+K) | O(K) | 穩(wěn)定 |
三，排序系列所有源代碼
Sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"Stack.h"
//打印
void PrintSort(int* arr, int n);
//插入排序
void InsertSort(int* arr, int n);
//希爾排序
void HillSort(int* arr, int n);
//選擇排序
void SeleSort(int* arr, int n);
//堆排序
void HeapSort(int* arr, int n);
//向下調(diào)整
void DownAdjust(int* arr, int n, int i);
冒泡排序
//void BubblSort(int* arr, int n);
//快速排序
void QuickSort(int* arr, int begin, int end);
//三數(shù)取中
int middle(int* arr, int left, int right);
//快慢指針法
int PartSort3(int* arr, int left, int right);
//挖坑法
int PartSort2(int* arr, int left, int right);
//霍爾排序
int PartSort1(int* arr, int left, int right);
//快速排序(非遞歸)
void QuickNon(int* arr, int begin, int end);
//歸并排序
void MergerSort(int* arr, int begin, int end);
//歸并排序(非遞歸)
void MergerSortNon(int* arr, int begin, int end);
// 計數(shù)排序
void CountSort(int* arr, int n);
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//打印
void PrintSort(int* arr, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//插入排序
void InsertSort(int* arr, int n)
{
int i = 0;
for (i = 0; i < n-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] >= tmp)
{
//交換
Swap(&arr[end], &arr[end+1]);
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//希爾排序
void HillSort(int* arr, int n)
{
int gap = n;
int i = 0;
while (gap > 1)
{
gap = gap / 2;
for (i = 0; i < n-gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] >= tmp)
{
//交換
Swap(&arr[end], &arr[end + gap]);
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
//選擇排序
void SeleSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
Swap(&arr[begin], &arr[mini]);
// 如果maxi和begin重疊，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&arr[end], &arr[maxi]);
++begin;
--end;
}
}
//向下調(diào)整
void DownAdjust(int* arr, int n, int i)
{
int perent = i;
int child = perent* 2 + 1;
while (child<n)
{
if (child+1<n && arr[child + 1] > arr[child])
{
child++;
}
if (arr[perent] < arr[child])
{
//交換
Swap(&arr[perent], &arr[child]);
perent = child;
child = perent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* arr, int n)
{
//建堆
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
//向下調(diào)整
DownAdjust(arr, n, i);
}
//交換，刪除排序法
while (n > 1)
{
//交換
Swap(&arr[0], &arr[n - 1]);
n--;
//向下調(diào)整
DownAdjust(arr, n, 0);
}
}
//三數(shù)取中
int middle(int* arr, int left, int right)
{
//int mid = (left +right)/ 2;
//隨機數(shù)取中
int mid = left + (rand() % (right - left));
if (arr[left] < arr[mid])
{
if (arr[mid] < arr[right])
{
return mid;
}
if (arr[left] < arr[right])
{
return right;
}
else
{
return left;
}
}
//arr[mid]<=arr[left]
else
{
if (arr[mid] > arr[right])
{
return mid;
}
if (arr[left] > arr[right])
{
return right;
}
else
{
return left;
}
}
}
//霍爾排序
int PartSort1(int* arr, int left, int right)
{
//三數(shù)取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int keyi = left;
while (left < right)
{
//右邊先走
while (left<right && arr[right]>=arr[keyi])
{
right--;
}
//左邊后走
while (left < right && arr[left] <= arr[keyi])
{
left++;
}
//交換
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);
return left;
}
//挖坑法
int PartSort2(int* arr, int left, int right)
{
//三數(shù)取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int key = arr[left];
int hole = left;
while (left < right)
{
while (left < right && arr[right] >= key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
//前后指針法
int PartSort3(int* arr, int left, int right)
{
//三數(shù)取中
int ret = middle(arr, left, right);
Swap(&arr[left], &arr[ret]);
int keyi = left;
int slow = left, fast = left+1;
while (fast<=right)
{
if (arr[fast] < arr[keyi] && ++slow!=fast)
{
//交換
Swap(&arr[fast], &arr[slow]);
}
fast++;
}
Swap(&arr[slow], &arr[keyi]);
return slow;
}
//插入排序(改造版)
void InsertSort1(int* arr, int left, int right)
{
int i = 0;
for (i = left; i < right; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] >= tmp)
{
//交換
Swap(&arr[end], &arr[end + 1]);
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//快速排序
void QuickSort(int* arr, int begin, int end)
{
srand(time(0));
if (begin >= end)
{
return NULL;
}
if (end - begin <10)
{
InsertSort1(arr,begin,end);
}
else
{
int keyi = PartSort1(arr, begin, end);
//排序[begin,keyi) & [keyi+1,end]
QuickSort(arr, begin, keyi);
QuickSort(arr, keyi + 1, end);
}
}
//快速排序(非遞歸)
void QuickNon(int* arr, int begin, int end)
{
srand(time(0));
ST ps;
//初始化
STInit(&ps);
if (begin >= end)
{
return;
}
//插入
STPush(&ps, end);
STPush(&ps, begin);
//棧不為空就進去
while (!STEmpty(&ps))
{
int left = STInsert(&ps);//棧頂元素
STPop(&ps);//刪除
int right = STInsert(&ps);
STPop(&ps);
int keyi = PartSort1(arr, left, right);
//排序[left,keyi-1] & [keyi+1,right]
if (keyi + 1 < right)
{
//插入
STPush(&ps, right);
STPush(&ps, keyi + 1);
}
if (left < keyi - 1)
{
//插入
STPush(&ps, keyi - 1);
STPush(&ps, left);
}
}
//銷毀
STDestroy(&ps);
}
//歸并
void Merger(int* arr, int* tmp,int begin,int end)
{
int mid = (begin + end) / 2;
if (begin == end)
{
return;
}
//排序【begin,mid】& 【mid+1,end】
Merger(arr, tmp, begin,mid);
Merger(arr, tmp, mid+1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = 0;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while(begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//進行拷貝
memcpy(arr + begin, tmp, (end - begin+1)*sizeof(int));
}
//歸并排序
void MergerSort(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
//開辟同等大小數(shù)組
int* tmp = (int*)malloc((end - begin + 1)*sizeof(int));
//歸并
Merger(arr, tmp, begin, end);
free(tmp);
tmp = NULL;
}
//歸并排序(非遞歸)
void MergerSortNon(int* arr, int begin, int end)
{
if (begin >= end)
{
return;
}
//開辟同等大小數(shù)組
int* tmp = (int*)malloc((end - begin + 1) * sizeof(int));
int gap = 1;
int j = 0;
while (gap < end)
{
for (j = 0; j < end; j += 2 * gap)
{
int begin1 = j, end1 = begin1+gap-1;
int begin2 =end1+1, end2 = begin2+gap-1;
int i = 0;
//處理邊界問題
if (end1 >= end)
{
break;
}
if (end2 >end)
{
end2 = end;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//進行拷貝
memcpy(arr + j, tmp, (end2 - j+ 1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
// 計數(shù)排序
void CountSort(int* arr, int n)
{
int i = 0;
int max = arr[0], min = arr[0];
//找最大，最小值
for (i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//空間大小
int sum = max - min + 1;
//開辟空間并且使元素值都為0
int* arr1 = (int*)calloc(sum, sizeof(int));
//給新數(shù)組賦值
for (i = 0; i < n; i++)
{
arr1[arr[i] - min]++;
}
int j = 0;
//回收到原來的序列中
for (i = 0; i < sum; i++)
{
while (arr1[i]--)
{
arr[j++] = i + min;
}
}
}Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct StackTop
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//刪除
void STPop(ST* ps);
//返回棧頂
STDataType STInsert(ST* ps);
//數(shù)量
int STSize(ST* ps);
//判斷是否為空
int STEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//銷毀
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//插入
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
ps->capacity = ps->top == 0 ? 4 : ps->capacity*2;
ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*ps->capacity);
}
ps->a[ps->top] = x;
ps->top++;
}
//刪除
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//返回棧頂
STDataType STInsert(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top-1];
}
//數(shù)量
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判斷是否為空
int STEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
{
return 1;
}
else
{
return 0;
}
}
同志們！排序的知識就到這里了！
后面博主會陸續(xù)更新；
如有不足之處歡迎來補充交流！
完結(jié)。。文章來源：http://www.zghlxwxcb.cn/news/detail-715780.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-715780.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】計數(shù)排序 & 排序系列所有源代碼 & 復(fù)雜度分析（終章）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
