国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

當(dāng)前位置: 首頁 > news >正文

能打開任何網(wǎng)站瀏覽器下載百度店鋪

能打開任何網(wǎng)站瀏覽器下載,百度店鋪,曹鵬wordpress,wordpress自定義主頁排序算法 前言一、認(rèn)識(shí)排序排序的概念常見的排序算法排序?qū)崿F(xiàn)的接口 二、常見排序算法的實(shí)現(xiàn)插入排序直接插入排序希爾排序 選擇排序直接選擇排序堆排序 交換排序冒泡排序 三、各個(gè)排序的效率比較四、完整代碼演示:shell_insert.hshell_insert.ctest.c 總結(jié) 前言 來…

在這里插入圖片描述

排序算法

  • 前言
  • 一、認(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é):

  1. 元素集合越接近有序,直接插入排序算法的時(shí)間效率越高
  2. 時(shí)間復(fù)雜度:O(N^2)
  3. 空間復(fù)雜度:O(1),它是一種穩(wěn)定的排序算法
  4. 穩(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é):

  1. 直接選擇排序思考非常好理解,但是效率不是很好。實(shí)際中很少使用
  2. 時(shí)間復(fù)雜度:O(N^2)
  3. 空間復(fù)雜度:O(1)
  4. 穩(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é):

  1. 堆排序使用堆來選數(shù),效率就高了很多。
  2. 時(shí)間復(fù)雜度:O(N*logN)
  3. 空間復(fù)雜度:O(1)
  4. 穩(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é):

  1. 冒泡排序是一種非常容易理解的排序
  2. 時(shí)間復(fù)雜度:O(N^2)
  3. 空間復(fù)雜度:O(1)
  4. 穩(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ò)!

http://m.aloenet.com.cn/news/34193.html

相關(guān)文章:

  • 莆田網(wǎng)站建設(shè)網(wǎng)絡(luò)營銷策劃書格式
  • 臨時(shí)手機(jī)號(hào)注冊(cè)網(wǎng)站百度top排行榜
  • 延安有哪些做網(wǎng)站的公司wifi優(yōu)化大師下載
  • 女女做那個(gè)動(dòng)漫視頻網(wǎng)站做網(wǎng)絡(luò)推廣一個(gè)月的收入
  • 一級(jí)a做爰片免費(fèi)網(wǎng)站中國片互聯(lián)網(wǎng)營銷有哪些方式
  • 品牌推廣網(wǎng)站怎樣做關(guān)鍵詞優(yōu)化排名查詢
  • 網(wǎng)站菜單導(dǎo)航怎么做網(wǎng)站seo優(yōu)化免費(fèi)
  • 恒網(wǎng)做的網(wǎng)站網(wǎng)站排名優(yōu)化服務(wù)公司
  • wordpress 設(shè)置數(shù)據(jù)庫南陽網(wǎng)站seo
  • 太原seo網(wǎng)站排名網(wǎng)站優(yōu)化包括
  • 成都網(wǎng)站建設(shè)哪里好點(diǎn)seo1短視頻網(wǎng)頁入口營銷
  • 深圳網(wǎng)站制作公司咨詢小紅書搜索關(guān)鍵詞排名
  • 亞馬遜虛擬主機(jī)做網(wǎng)站最新清遠(yuǎn)發(fā)布
  • 怎么給自己的網(wǎng)站做模版全網(wǎng)營銷推廣平臺(tái)有哪些
  • 羅湖網(wǎng)站建設(shè)羅湖網(wǎng)站設(shè)計(jì)seo是什么意思為什么要做seo
  • 網(wǎng)站要咋做2022年最新熱點(diǎn)素材
  • 免費(fèi)做h5的網(wǎng)站展示型網(wǎng)站有哪些
  • 做室內(nèi)設(shè)計(jì)的網(wǎng)站有哪些內(nèi)容數(shù)字營銷服務(wù)商seo
  • 日本設(shè)計(jì)創(chuàng)意網(wǎng)站web網(wǎng)站設(shè)計(jì)
  • 萊蕪網(wǎng)站優(yōu)化招聘網(wǎng)seo搜索如何優(yōu)化
  • 學(xué)用mvc做網(wǎng)站重慶seo網(wǎng)絡(luò)推廣優(yōu)化
  • vue做移動(dòng)端網(wǎng)站與pc端有什么區(qū)別網(wǎng)站推廣軟件免費(fèi)版下載
  • 網(wǎng)站開發(fā)的項(xiàng)目開發(fā)網(wǎng)站開發(fā)公司排行榜
  • 品牌廣告設(shè)計(jì)制作公司網(wǎng)站源碼班級(jí)優(yōu)化大師的功能有哪些
  • wordpress使用兩個(gè)主題如何推廣seo
  • 獨(dú)立站都有哪些百度快速排名提升
  • 網(wǎng)站投票活動(dòng)怎么做百度域名注冊(cè)查詢
  • 沒有網(wǎng)站怎么做seob站推廣平臺(tái)
  • 網(wǎng)站報(bào)名怎么做市場營銷培訓(xùn)
  • 網(wǎng)站目錄鏈接怎么做天津百度推廣電話