史上最全的排序演算法講解--作為程式員的你一定要知道

一、冒泡排序演算法
演算法性質：1、時間復雜度：O(n2) 2、空間復雜度：O(1) 3、穩定排序 4、原地排序
程序簡單描述:
1、把第一個元素與第二個元素比較，如果第一個比第二個大，則交換他們的位置，接著繼續比較第二個與第三個元素，如果第二個比第三個大，則交換他們的位置….

2、我們對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這樣一趟比較交換下來之后，排在最右的元素就會是最大的數，

3、除去最右的元素，我們對剩余的元素做同樣的作業，如此重復下去，直到排序完成，

4、為方便理解我還準備了動圖：

c代碼實作

int* bubbleSort1(int arr[] ,int n) 
{
if (arr == NULL || n < 2) {  return arr; }
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n - i - 1; j++)
    {
        if (arr[j + 1] < arr[j])
        {
            flag = 0;
           swap_2_num(arr[j + 1],arr[j]);
        }
    }
}
return arr;
}

冒泡排序改進版c

int* bubbleSort1(int arr[] ,int n) 
{
if (arr == NULL || n < 2) {  return arr; }
for (int i = 0; i < n; i++)
{
    int flag = 1; //標志位
    for (int j = 0; j < n - i - 1; j++)
    {
        if (arr[j + 1] < arr[j])
        {
            flag = 0;
           swap_2_num(arr[j + 1],arr[j]); 
           //swap_2_num交換兩個數函式
        }
    }
    //一趟下來是否發生位置交換
    if (flag) {break;}
}
return arr;
}

python代碼實作

def bubble_sort(mylist): 
	for i in range(0,len(mylist)-1): #n個元素 共有n-1趟
		for j in range (i+1,len(mylist)):
			if mylist[i]<mylist[j]:
				mylist[i],mylist[j] = mylist[j],mylist[i]
	return mylist

冒泡排序改進版-python

def bubble_advance(mylist): 
	for i in range(0,len(mylist)-1): #n個元素 共有n-1趟
		flag = True
		for j in range (i+1,len(mylist)):
			if mylist[i]>mylist[j]:
				flag = False
				mylist[i],mylist[j] = mylist[j],mylist[i]
		if flag:
			break
	return mylist

二、選擇排序
性質：1、時間復雜度：O(n2) 2、空間復雜度：O(1) 3、非穩定排序 4、原地排序
程序簡單描述：
1、首先，找到陣列中最小的那個元素
2、其次，將它和陣列的第一個元素交換位置(如果第一個元素就是最小元素那么它就和自己交換)，
3、其次，在剩下的元素中找到最小的元素，將它與陣列的第二個元素交換位置，
4、如此往復，直到將整個陣列排序，這種方法我們稱之為選擇排序，
為方便理解我還準備了動圖：

c代碼實作

int* selectSort(int a[],int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[min] > a[j]) 
            {
                min = j; 
            }
        }
        swap_2_num(a[i],a[min]);
    }
    return a;
}

python代碼實作

def choice(mylist):
	for i in range(0,len(mylist)-1):  #比較len-1趟.先選第一個為最小值
		index = i#選一個最小值     # 記錄最小數的索引
		for j in range(i+1,len(mylist)): #把最小值與后面的每一個進行比較
			if mylist[index] < mylist[j]:
				index = j ##改變最小值  i不是最小數時，將 i 和最小數進行交換
		if index !=i: ##如果最小值有變 則對調
			mylist[index] ,mylist[i] =mylist[i] ,mylist[index]
	return mylist

三、插入排序
性質：1、時間復雜度：O(n2) 2、空間復雜度：O(1) 3、穩定排序 4、原地排序
我們在玩打牌的時候，你是怎么整理那些牌的呢？一種簡單的方法就是一張一張的來，將每一張牌插入到其他已經有序的牌中的適當位置，當我們給無序陣列做排序的時候，為了要插入元素，我們需要騰出空間，將其余所有元素在插入之前都向右移動一位，這種演算法我們稱之為插入排序，

程序簡單描述：
1、從陣列第2個元素開始抽取元素，
2、把它與左邊第一個元素比較，如果左邊第一個元素比它大，則繼續與左邊第二個元素比較下去，直到遇到不比它大的元素，然后插到這個元素的右邊，
3、繼續選取第3，4，….n個元素,重復步驟 2 ，選擇適當的位置插入，
為方便理解我還準備了動圖：

c代碼實作

int * insertsort(int arr[],int len)
{
    if (arr == NULL || len < 2) { return arr; }
    for (int i =1;i<len;i++)
    {
        int index = i;
        while (index>0 && arr[index]<arr[index-1])
        { 
            swap_2_num(arr[index],arr[index-1]);
            index -=1;
        }
    }
    return arr;
}

python代碼實作

def insert_sort(arr): 
	for i in range(1,len(arr)):
		index = i
		while index>0 and  arr[index-1] > arr[index]:
			(arr[index],arr[index-1]) = (arr[index-1],arr[index])
			index =index-1
	return arr

后續進步補充…

參考鏈接 1
參考鏈接2