能打開任何網(wǎng)站瀏覽器下載百度店鋪
排序算法
- 前言
- 一、認(rèn)識(shí)排序
- 排序的概念
- 常見的排序算法
- 排序?qū)崿F(xiàn)的接口
- 二、常見排序算法的實(shí)現(xiàn)
- 插入排序
- 直接插入排序
- 希爾排序
- 選擇排序
- 直接選擇排序
- 堆排序
- 交換排序
- 冒泡排序
- 三、各個(gè)排序的效率比較
- 四、完整代碼演示:
- shell_insert.h
- shell_insert.c
- test.c
- 總結(jié)
前言
來嘍來嘍~ 二叉樹的層序遍歷來嘍~
層序遍歷那是相當(dāng)有趣滴!
我的朋友,請(qǐng)不要迷惘,你要記住,你終有鯤鵬一日!
加油吧!從現(xiàn)在開始~
一、認(rèn)識(shí)排序
排序的概念
排序: 所謂排序,就是使一串記錄,按照其中的某個(gè)或某些關(guān)鍵字的大小,遞增或遞減的排列起來的操作。
穩(wěn)定性: 假定在待排序的記錄序列中,存在多個(gè)具有相同的關(guān)鍵字的記錄,若經(jīng)過排序,這些記錄的相對(duì)次序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱這種排序算法是穩(wěn)定的;否則稱為不穩(wěn)定的。
內(nèi)部排序: 數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序: 數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中,根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
常見的排序算法
排序?qū)崿F(xiàn)的接口
后面我們?cè)賮韺?duì)這些算法接口進(jìn)行實(shí)現(xiàn)!
// 插入排序
void InsertSort(int* a, int n);
// 希爾排序
void ShellSort(int* a, int n);
// 選擇排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
二、常見排序算法的實(shí)現(xiàn)
插入排序
基本思想:
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中,直到所有的記錄插入完為止,得到一個(gè)新的有序序列 。
這就像是什么呢?對(duì)啦!這就像是我們玩撲克牌時(shí)將紙牌排序一樣
直接插入排序
當(dāng)插入第i(i>=1)個(gè)元素時(shí),前面的array[0],array[1],…,array[i-1]已經(jīng)排好序,此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較,找到插入位置即將array[i]插入,原來位置上的元素順序后移
代碼實(shí)現(xiàn):
void InsertSort(int* a, int n) {// [0,end]有序,把end+1位置的插入到前序序列// 控制[0,end+1]有序for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end])//如果小于則將a[end]復(fù)制覆蓋到后一位,tmp保存被覆蓋的值{a[end + 1] = a[end];}else{break;}--end;//每次都往前比較}a[end + 1] = tmp;//將tmp保存值插入比它小的值的前面一位}
}
直接插入排序的特性總結(jié):
- 元素集合越接近有序,直接插入排序算法的時(shí)間效率越高
- 時(shí)間復(fù)雜度:O(N^2)
- 空間復(fù)雜度:O(1),它是一種穩(wěn)定的排序算法
- 穩(wěn)定性:穩(wěn)定
希爾排序
例:動(dòng)圖中g(shù)ap=n/2
圖例:
代碼實(shí)現(xiàn)
void ShellSort(int* a, int n) {int gap = n;while (gap > 1)//當(dāng)gap<=1則說明已經(jīng)進(jìn)行了最后的插入排序{gap = gap / 3 + 1;//gap每次縮小相應(yīng)倍數(shù),使得排序越來越接近有序,//+1使得gap最后一次排序?yàn)橹苯硬迦肱判?/span>for (int i = 0; i < n - gap; ++i){int end = i;//end為該次排序起始位置下標(biāo)int tmp = a[end + gap];//每次間隔gap個(gè)位置進(jìn)行比較while (end >= 0)//此處為直接插入思想{if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//a[end + gap] = tmp;}}
}
希爾排序的特性總結(jié):
穩(wěn)定性:不穩(wěn)定
希爾排序是對(duì)直接插入排序的優(yōu)化。
當(dāng)gap > 1時(shí)都是預(yù)排序,目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí),數(shù)組已經(jīng)接近有序的了,這就會(huì)很快。這樣整體而言,可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對(duì)比。*
希爾排序的時(shí)間復(fù)雜度不好計(jì)算,因?yàn)間ap的取值方法很多,導(dǎo)致很難去計(jì)算,因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定:
選擇排序
基本思想:
每一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素,存放在序列的起始位置,直到全部待排序的數(shù)據(jù)元素排完 。
直接選擇排序
在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
若它不是這組元素中的最后一個(gè)(第一個(gè))元素,則將它與這組元素中的最后一個(gè)(第一個(gè))元素交換在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重復(fù)上述步驟,直到集合剩余1個(gè)元素
代碼實(shí)現(xiàn):
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;//記錄末尾和開始位置while (begin < end)//當(dāng)begin小于end說明數(shù)組沒有被完全排序{// [begin, end]int mini = begin, maxi = begin;//將開始位置的值的下標(biāo)賦予mini,maxifor (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi])//比開始位置值大則maxi記錄這一位置的下標(biāo){maxi = i;}if (a[i] < a[mini])//比開始位置值小則mini記錄這一位置的下標(biāo){mini = i;}}Swap(&a[begin], &a[mini]);//最小值與開始值交換// max如果被換走了,修正一下if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}
直接選擇排序的特性總結(jié):
- 直接選擇排序思考非常好理解,但是效率不是很好。實(shí)際中很少使用
- 時(shí)間復(fù)雜度:O(N^2)
- 空間復(fù)雜度:O(1)
- 穩(wěn)定性:不穩(wěn)定
堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆,排降序建小堆。
對(duì)于堆排序不熟悉的話可以看看前面的文章哦!
堆排序
代碼實(shí)現(xiàn):
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 找出小的那個(gè)孩子if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下調(diào)整建堆// O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
堆排序的特性總結(jié):
- 堆排序使用堆來選數(shù),效率就高了很多。
- 時(shí)間復(fù)雜度:O(N*logN)
- 空間復(fù)雜度:O(1)
- 穩(wěn)定性:不穩(wěn)定
交換排序
基本思想: 所謂交換,就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置,交換排序的特點(diǎn)是:將鍵值較大的記錄向序列的尾部移動(dòng),鍵值較小的記錄向序列的前部移動(dòng)。
冒泡排序
冒泡排序應(yīng)該是大家最熟悉的排序方式了吧!
代碼實(shí)現(xiàn):
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int exchange = 0;//設(shè)置一個(gè)初值為0的變量,看這一次排序數(shù)組是否有變化for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;//如果發(fā)生了交換,則將exchange的值變?yōu)?}}if (exchange == 0)//exchange為0的話說明這一趟排序數(shù)組是有序的//所以跳出這一趟循環(huán){break;}}
}
冒泡排序的特性總結(jié):
- 冒泡排序是一種非常容易理解的排序
- 時(shí)間復(fù)雜度:O(N^2)
- 空間復(fù)雜度:O(1)
- 穩(wěn)定性:穩(wěn)定
三、各個(gè)排序的效率比較
測試函數(shù)的定義
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = N - 1; i >= 0; --i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();SelectSort(a5, N);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("SelectSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}
測試結(jié)果:
從這次時(shí)間效率來看
堆排序>希爾排序>直接插入>選擇排序>冒泡排序
四、完整代碼演示:
shell_insert.h
#pragma once
#include<stdio.h>
void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void BubbleSort(int* a, int n);
void HeapSort(int* a, int n);
void SelectSort(int* a, int n);
shell_insert.c
#include "shell_insert.h"void PrintArray(int*a,int n) {for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void Swap(int* x, int* y) {int tmp = *x;*x = *y;*y = tmp;
}void InsertSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];}else{break;}--end;}a[end + 1] = tmp;}
}void ShellSort(int* a, int n) {int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int exchange = 0;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0){break;}}
}void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}
test.c
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = N - 1; i >= 0; --i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();SelectSort(a5, N);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("SelectSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}int main()
{TestOP();return 0;
}
總結(jié)
今天的學(xué)習(xí)就到這里吧!
排序是一個(gè)相當(dāng)有趣的課程!
相信大家學(xué)習(xí)完了之后也有與我相同的感受吧!
本篇文章圖片部分來自網(wǎng)絡(luò)!