C++選擇排序算法實(shí)例詳解
本文實(shí)例為大家分享了C++選擇排序算法的具體代碼,供大家參考,具體內(nèi)容如下
基本思想
每一趟從無(wú)序區(qū)中選出最小的元素,順序放在有序區(qū)的最后,直到全部元素排序完畢。
由于選擇排序每一趟總是從無(wú)序區(qū)中選出全局最?。ɑ蜃畲螅┑脑兀赃m用于從大量元速度中選擇一部分排序元素。例如,從10000個(gè)元素中選出最小的前10位元素。
直接選擇排序
1.排序思路
從第i趟開(kāi)始,從當(dāng)前無(wú)序區(qū)arr[i…n-1]中選出最小元素arr[k],將它與有序區(qū)的最后一個(gè)元素,也就是無(wú)序區(qū)的第一個(gè)元素交換。每趟排序后,有序區(qū)增加一個(gè)元素,無(wú)序區(qū)減少一個(gè)元素,且有序區(qū)中所有元素均小于等于無(wú)序區(qū)中的元素。經(jīng)過(guò)n-1趟排序后,無(wú)序區(qū)只剩下arr[n-1]一個(gè)元素,它必然為整個(gè)序列的最大值,故無(wú)需再排。
2.排序算法
void SelectSort(int *arr, int size) { if (arr == NULL) return; //1.找到無(wú)序區(qū)中最小的元素和它的下標(biāo) int i, j; for (i = 0; i < size - 1; i++) { int k = i; for (j = i + 1; j < size; j++) { if (arr[j] < arr[k]) { k = j; } } //2.把最小的元素與無(wú)序區(qū)第一個(gè)元素交換 //swap(arr[i], arr[k]); if (k != i) { int tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } } }
3.算法分析
由于要選出最小值,故無(wú)序區(qū)中的每個(gè)元素都要參與比較,所以無(wú)論初始數(shù)據(jù)序列的狀態(tài)如何,總的比較次數(shù)為:
C = n-1 +n-2+n-3+…+2+1 = n(n-1)/2
故直接選擇排序的時(shí)間復(fù)雜度為O(N^2),空間復(fù)雜度為O(1)。直接選擇排序是一個(gè)不穩(wěn)定的算法。例如,排序序列為{5,3,2,5,4,1},第一趟排序后得到{1,3,4,5,4,5},兩個(gè)5的相對(duì)位置發(fā)生了變化。
4.優(yōu)化版本
每趟排序同時(shí)找出最大值和最小值,把最小值放在序列的左邊,最大值放在序列的右邊,然后同時(shí)縮小左右排序范圍。
//優(yōu)化,每趟排序同時(shí)找出最大值和最小值 void SelectSort1(int *arr, int size) { if (arr == NULL) return; int left = 0; int right = size - 1; while (left < right) { for (int i = left; i < right; i++) { if (arr[i] < arr[left]) swap(arr[i], arr[left]); if (arr[i] > arr[right]) swap(arr[i], arr[right]); } left++; right--; } }
堆排序
1.排序思路
堆排序是一種樹(shù)形選擇排序方法,在排序過(guò)程中,將arr[0…n-1]看成一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹(shù)中雙親節(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無(wú)序區(qū)中選擇最大(或最?。┑脑?。
下標(biāo)從0開(kāi)始,節(jié)點(diǎn)i的兩個(gè)孩子節(jié)點(diǎn)可表示為2*i+1、2*i+2。
2.排序算法
void AdjustDown(int *arr, int size, int parent) { int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[parent] < arr[child]) { swap(arr[parent], arr[child]); parent = child; child = 2 * parent + 1; } else break; } } void HeapSort(int *arr, int size) { if (arr == NULL) return; //1.建立初始堆(此處為大堆) int root; for (root = (size / 2)-1; root >= 0; root--) { AdjustDown(arr, size, root); } //2.將arr[0]與arr[n-1]交換,然后再調(diào)整arr[0...n-1],使其滿(mǎn)足大堆,如此反復(fù)操作 for (root = size-1; root >= 1; root--) { swap(arr[root], arr[0]); AdjustDown(arr, root, 0); } }
3.算法分析
堆排序的時(shí)間主要由建堆和反復(fù)調(diào)整堆這兩部分的時(shí)間構(gòu)成,由于可以把堆看成完全二叉樹(shù)的結(jié)構(gòu),所以堆排序的時(shí)間復(fù)雜度為O(N*lgN),空間復(fù)雜度為O(1),堆排序算法不穩(wěn)定。
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C 語(yǔ)言基礎(chǔ)之C語(yǔ)言的常見(jiàn)關(guān)鍵字
C語(yǔ)言中有一些預(yù)先定義的字符串,他們本身被賦予了自身的功能。并且我們?cè)诙x變量的時(shí)候,不能去搶他們的名字來(lái)用。他們就是今天的主角:關(guān)鍵字,下面文章將給大家做詳細(xì)介紹2021-09-09利用Matlab實(shí)現(xiàn)時(shí)域分析功能的示例詳解
利用MATLAB可以方便地進(jìn)行控制系統(tǒng)的時(shí)域分析。這篇文章主要通過(guò)簡(jiǎn)單的示例為大家介紹了Matlab進(jìn)行時(shí)域分析的具體操作,需要的可以參考一下2023-02-02C/C++程序開(kāi)發(fā)中實(shí)現(xiàn)信息隱藏的三種類(lèi)型
這篇文章主要介紹了C/C++程序開(kāi)發(fā)中實(shí)現(xiàn)信息隱藏的三種類(lèi)型的相關(guān)資料,需要的朋友可以參考下2016-02-02詳解如何將Spire.PDF for C++集成到C++程序中
Spire.PDF for C++ 是一個(gè)專(zhuān)業(yè)的 PDF 庫(kù),供開(kāi)發(fā)人員在任何類(lèi)型的 C++ 應(yīng)用程序中閱讀、創(chuàng)建、編輯和轉(zhuǎn)換 PDF 文檔,本文主要介紹了兩種不同的方式將 Spire.PDF for C++ 集成到您的 C++ 應(yīng)用程序中,希望對(duì)大家有所幫助2023-11-11如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本
這篇文章主要介紹了如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本的方法,需要的朋友可以參考下2021-04-04