常見排序之平方排序(時間複雜度)

捕獲一只小肚皮 2021-09-19 23:10:52 阅读数:187

排序 平方 排序

typora-copy-images-to: upload


前言

此篇文章介紹的排序主要有3個,冒泡排序,選擇排序,插入排序,他們有一個共同的特點,那就是時間複雜度都為O(n²).


冒泡排序

冒牌排序的思想是,先遍曆數組一次,在遍曆過程中,通過兩兩交換的方式把較大的數據放到後面(保證了每次遍曆時都能把最大的數放在後面),然後又從頭到尾重複此過程,直到有序.如下圖(綠色代錶在遍曆過程中兩兩比較,柳丁色代錶已經部分排好序):

1391679-20180618163321525-1936669878

知道了思想,怎麼寫代碼呢,我們先從最簡單的一步開始,即只遍曆一次,該怎麼寫,先看看需求:

  • 兩兩交換,說明需要一個交換函數.
  • 什麼時候需要交換呢?當前者大於後者的時候,也就是說我們需要比較.

所以如果只遍曆一次,代碼如下:

void swap(int* a,int* b)
{

int tmp = *a;
*a = *b;
*b = tmp;
}
//n是數組長度
for(int j = 0;j<n-1;j++) //小於n-1是因為索引最大為n-1,j代錶當前索引,那麼j最大只能為n-2
{

if(num[j] > num[j+1]) //如果前者大於後者就交換,否則繼續遍曆.
{

swap(&num[j],&num[j+1]);
}
}

現在我們結合遍曆一次的代碼和上面的動圖仔細想想,既然遍曆一次就調整好一個最大的數字在最後面,那麼我們要遍曆多少次才能把全部的數字排好序呢?沒錯,答案是n-1次,因為有n個數字,但是是通過兩兩比較實現的,**當索引[1,n-1]**都有序後,索引為0的數字一定比索引為1的數字小,就不需要再比較了.

所以冒泡排序的代碼如下:

void BubbleSort(int num[],int n)
{

for(int i = 0;i<n-1;i++) //需要遍曆n-1次
{

//n是數組長度
for(int j = 0;j< n-1 - i;j++) //小於n-1-i是因為每一次完整遍曆數組後,最後一個數字一定是最大的,下一次遍曆就不需要再管它.
{

if(num[j] > num[j+1]) //如果前者大於後者就交換,否則繼續遍曆.
{

swap(&num[j],&num[j+1]);
}
}
}
}

測試:

image-20210918221811223

選擇排序

選擇排序的思想是,先假設未排序第一元素是最小的,然後遍曆一遍數組看是否有比假想的最小數更小的數,如果有就記錄索引,遍曆完成以後把真正的最小數與最初的假想最小數交換.然後繼續重複上面過程.如下圖(綠色代錶正在遍曆,紅色代錶定比特最小數,柳丁色代錶部分排好序):

20210711213326712

同樣道理,我們由簡到繁,先寫出只遍曆一次時候的代碼,那麼只遍曆一次時候需要的准備是:

  • 用於記錄最小元素的索引變量min_index.
  • 交換函數.

代碼如下:

//n是數組長度
int min_index = 0; //0代錶未排序元素的頭的索引.
for(int j = 0 + 1;j<n;j++) //j從頭的下一個比特置開始
{

if(num[j] < num[min_index]) //如果當前元素比最小元素小
{

min_index = j; //就記錄最下元素的索引
}
}
swap(&num[0],&num[min_index]); //最小元素與頭進行交換.

這個和冒泡排序是不是幾乎一樣?遍曆一次便能够確定一個最小的數,然後放到首比特,那麼需要多少次呢?答案是n-1次

所以完整的代碼如下:

void SelectSort(int num[],int n)
{

for(int i = 0;i<n-1;i++) //需要遍曆n-1次
{

int min_index = i; //i代錶 未排序元素 的頭的索引.
for(int j = i + 1;j<n;j++) //j從頭的下一個比特置開始
{

if(num[j] < num[min_index]) //如果當前元素比最小元素小
{

min_index = j; //就記錄最下元素的索引
}
}
swap(&num[i],&num[min_index]); //最小元素與頭進行交換.
}
}

測試:

image-20210918225925154

插入排序

插入排序的思想是,從索引j(範圍為1到n-1)開始,保證[0,i]區間的元素有序,怎麼保證呢? 先把索引為i的元素保存下來(變量target),然後依次往前比較,如果前面的元素比target大,就往後放,否則停止.如圖(柳丁色代錶部分有序,綠色代錶從i開始往前遍曆,紅色代錶原索引i元素):

1391679-20180618165919523-196396537

仍然一樣的思想,先從簡到繁,如若只執行一次,該怎樣操作?

int target = num[i]; //索引為[0,i]區間中索引為i的元素
int aim = i; //aim是用於記錄target真正應該的比特置
for(int j = i;j>0;j--)
{

if(num[j-1] > target) num[j] = num[j-1],aim = j-1;//如果前面大於target,前面就覆蓋後面,並且aim更新比特置.
}
num[aim] = target; //target回到自己應該的比特置.

現在我們看向上圖,可以發現,i是從1開始遞增的.所以完整代碼為:

void InsertSort(int num[],int n)
{

for(int i =1;i<n;i++)
{

int target = num[i]; //索引為[0,i]區間中索引為i的元素
int aim = i; //aim是用於記錄target真正應該的比特置
for(int j = i;j>0;j--)
{

if(num[j-1] > target) num[j] = num[j-1],aim = j-1;//如果前面大於target,前面就覆蓋後面,並且aim更新比特置.
}
num[aim] = target; //target回到自己應該的比特置.
}
}

測試

image-20210919095315705

冒泡排序優化

大家有沒有想過,對於冒泡排序,如果數據本來就是有序的,是沒必要再比下去的,但是冒泡排序卻不得不仍然要比n*(n-1)/2次,所以我們給其加個flag,第一遍遍曆時判斷是否有序,如果有序,就結束.

void BubbleSort(int num[],int n)
{

for(int i = 0;i<n-1;i++) //需要遍曆n-1次
{

int flag = 1; //等於1代錶假設是有的
for(int j = 0;j< n-1 - i;j++)
{

if(num[j] > num[j+1])
{

swap(&num[j],&num[j+1]);
flag = 0; //如果交換了數字,說明無效,變為0;
}
}
if(flag) break;//如果有序就停止
}
}

選擇排序優化

受到上面冒泡排序的啟示,大家可能會想,如果有序就怎麼樣…但是這種形式的優化對於選擇排序來說是沒有意義的,因為根本無法達到.

那麼優化選擇排序是優化的哪些呢?

選擇的思路是把最小的放到最前面,那麼我們可不可以在遍曆一次的時候同時找到最大和最小呢?然後最小放前面,最大放後面呢?

void SelectSort(int num[],int n)
{

for(int i = 0;i<n-1;i++)
{

int min_index = i; //假設索引為i元素最小
int max_index = i; //假設索引為i元素最大
for(int j = i + 1;j < n-i;j++) //j小於n-i是因為最後面的元素在逐漸有序,便不需要再管
{

if(num[j] < num[min_index])
{

min_index = j; //更新最小
}
if(num[j] > num[max_index])
{

max_index = j; //更新最大
}
}
swap(&num[i],&num[min_index]); //把最小的放前面
if(max_index == i) max_index = min_index; //如果最大值在頭,那麼最小值放在前面後,最大值就被換到min_index比特置
swap(&num[n-1-i],&num[max_index]);//最大的放後面
}
}

插入排序優化

大家想想,插入排序可以怎麼優化呢?其實插入排序由於自身的特性,幾乎優化不了,比如數據有序,插入排序遍曆一遍就知道了,那我們說的插入排序優化是什麼呢?這個博主會放到另一篇文章講,因為插入的改進後就是另一個排序,希爾排序

版权声明:本文为[捕獲一只小肚皮]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919231051448y.html