十大經典排序算法

• 1. 相關術語介紹
• 2. 排序算法分類以及複雜度
• 3.排序算法詳解
• • 3.1冒泡排序
  • 3.2 選擇排序
  • 3.3 選擇排序

1. 相關術語介紹

穩定排序：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；

非穩定排序：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；

内排序：所有排序操作都在記憶體中完成；

外排序：由于資料太大，是以把資料放在磁盤中，而排序通過磁盤和記憶體的資料傳輸才能進行；

時間複雜度：排序所耗費的時間；

空間複雜度：排序所耗費的記憶體；

比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以也稱為非線性時間比較類排序。

非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。

2. 排序算法分類以及複雜度

排序算法分類

十大排序算法主要可以分為兩大類：1.比較類排序 2.非比較類排序，下面是排序算法的分類

不同排序算法的複雜度以及穩定性

3.排序算法詳解

3.1冒泡排序

下面對資料從小到大排序

思想：每次尋找一組資料中最大的元素，兩兩比較，找到後放到資料的最後一位。n個資料第一次兩兩比較n-1次。

第二次比較n-2次，比較的時候如果前一個元素比第二個元素大則互相交換。

總共兩層循環：第一層代表需對比幾輪；第二層代表需要兩兩對比多少次

以下面的圖舉例

15個數，第一輪兩兩對比49次找出15個數中最大的數50

第二輪兩兩對比48次找到次大數48

以此類推…

那總共需要多少輪呢？

15個數，需要14輪

每輪需要兩兩對比多少次呢？

很明顯，每輪兩兩對比的次數不固定

第一輪兩兩對比14次找到最大數

第二輪需要對比13次，因為不用和最後一個數對比

C語言代碼

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int BubbleSort(int arr[],int len)
{
	int temp = 0;
	for (int i = 0; i < len-1; i++)
	{
		for (int j = 0; j < len-1-i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	int len = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr,len);
	
}
           

3.2 選擇排序

選擇排序：每輪都找到一組資料中最小的數依次放在數組前面。

與冒泡排序的不同：冒泡排序在找數的時候，每次比較都需要進行資料交換，而選擇排序是兩兩對比 記錄資料 的索引，找到資料後隻進行一次交換。

以對{ 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 }由小到大排列為例

C語言代碼

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void selectionSort(int arr[], int len)
{
	int temp = 0;
	for (int i = 0; i < len-1; i++)
	{
		int index = i;
		for (int j = i+1; j < len; j++)
		{
			if (arr[j] < arr[index])
			{
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
}
int main()
{
	int arr[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	int len = sizeof(arr) / sizeof(arr[0]);
	selectionSort(arr, len);
}
           

3.3 選擇排序