国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【算法】計數排序 + 各個排序算法的穩定性

不知名網友 / 2171人閱讀

摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。

之前介紹的排序算法：

計數排序

計數排序是一個非基于比較的排序算法，該算法于1954年由Harold H. Seward提出

它的優勢在于在對一定范圍內的整數排序時，它的復雜度為Ο(n+k)（其中k是整數的范圍），快于任何比較排序算法

當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）

  • 時間復雜度：O(Max(N, Range))
  • 空間復雜度：O(range)
  • 適合范圍比較集中的整數數組
  • 范圍較大，或者是浮點數等等都不適合排序了

一、算法思路圖解

1. 計數

基本思路：遍歷數組a，a[i]下標對應的count[a[i]]++

  • count數組大小

    看樣子范圍應該是0到a數組中最大的數？

    實則不是，如果數字是

    1000， 1001， 1100

    則從0到1100 ，浪費了很多空間

    所以我們定義一個映射數組，所有的數字都是相對最小的數字的大小

    1000， 1001， 1100

    映射數組數字大小：a[i] - min

    0， 1， 100

    將它設置為count數組對應下標

2. 拷貝到原數組

這里主要是尋找數組下標與數組值之間的對應關系

  • count[i]，拷貝的數字是i + min進入原數組（返回映射）

  • count[i] 的數值表示，數字i需要拷貝到原數組的次數

  • 所以count數組初始值都為0

  • 拷貝一次count[i]–

二、代碼

//計數排序void CountSort(int* a, int n){	int max = a[0];	int min = a[0];	int i = 0;	//取出最大和最小值找范圍	for (i = 0; i < n; i++)	{		if (a[i] > max)		{			max = a[i];		}		if (a[i] < min) 		{			min = a[i];		}	}		//數組數字所在范圍	int range = max - min + 1;	//開辟內存空間，并且初始化為0	int* tmp = (int*)calloc(range, sizeof(int));		//malloc操作	//int* tmp = (int*)mallco(sizeof(int) * range);	//memset(tmp, 0, sizeof(int) * range);	if (!tmp)	{		printf("calloc fail/n");		exit(-1);	}	int* count = tmp;	//計數	for (i = 0; i < n; i++)	{		count[a[i] - min]++;	}	 	int j = 0;	//計數放回	for (i = 0; j < range; j++)	{		while (count[j]--)		{			a[i++] = j + min;		}	}	free(tmp);    tmp = NULL;}

三、測試

四、各個排序算法的穩定性

1. 穩定性定義

相同數值，在排序過后相對位置不發生改變

  • 前一個和后一個相同的數，排序完成之后他們還是前一個還是在后一個數之前

2. 是否穩定

  • 直接插入排序 穩定

    因為是按順序，從前往后，前1、2、3……個數依次插入排成有序

  • 希爾排序 不穩定

    因為是以x為長度，跨位置選數字組成一組開始插入排序

  • 選擇排序 不穩定

    選擇排序是按順序比較前后，挑出最大和最小。將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。

    但會有人說我可以通過控制代碼，來選擇第一次選到最大的那個是后面的那個數

    還有一種情況

    選擇排序算法中還有一段是這樣的，如果找到最大最小的兩個數，最大的數在最小數需要放的位置，先交換最大和最小，改變序號

  • 堆排序 不穩定

    看圖，向下調整之后位置改變

  • 冒泡排序 穩定

    前后兩個數交換，可以控制代碼使之相對位置不改變

  • 快速排序 不穩定

    假設最左為key，左邊找大，右邊找小

    相對位置發生改變

  • 歸并排序 穩定

    實質上細分來看是每個循環都是兩個數組，相對順序不變

    按照從小到大的順序歸并到一個數組，所以穩定

  • 計數排序 穩定

    統計相同數值的個數，按順序映射到原數組

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/125655.html

相關文章

  • JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

    摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學好前端，先練好內功，只有內功深厚者...

    Awbeci 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

    摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...

    zsy888 評論0 收藏0

  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀 排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...

    verano 評論0 收藏0

  • 數據結構與算法——線性排序

    摘要：實際上，桶排序的應用場景十分的有限，對數據的要求比較苛刻。極端情況下，如果數據全部劃分到一個桶內，就變成了非線性排序了。 1. 回顧 前面已經說完了幾種非線性排序，它們分別是時間復雜度為 O(n2) 、適合小規模數據的冒泡排序、選擇排序、插入排序，和應用較廣泛的時間復雜度為 O(nlogn) 的希爾排序、歸并排序、快速排序。其實這幾種排序都有一個特性，那就是它們都是基于數據的比較和移動...

    Allen 評論0 收藏0

  • PHP數組排序算法實現(14種)

    摘要：本文將介紹快速排序計數排序梳排序堆排序歸并排序希爾排序選擇排序插入排序地精排序聯合冒泡排序雞尾酒排序冒泡排序奇偶排序使用標志的冒泡排序種排序算法的實現。是一種不穩定的排序算法。 本文將介紹快速排序、計數排序、梳排序、堆排序、歸并排序、希爾排序、選擇排序、插入排序、地精排序、聯合冒泡排序、雞尾酒排序、冒泡排序、奇偶排序、使用標志的冒泡排序14種排序算法的實現。本文是由于閱讀了文章《測試評...

    aisuhua 評論0 收藏0

發表評論

0條評論

不知名網友

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<