排序代碼(python，c++) 及基本算法復雜度

0.導語

本節為手撕代碼系列之第一彈，主要來手撕排序算法，主要包括以下幾大排序算法：

直接插入排序
冒泡排序
選擇排序
快速排序
希爾排序
堆排序
歸并排序

1.直接插入排序

【算法思想】

每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止。

【代碼實現】

# 直接插入排序
def insert_sort(arr):length = len(arr)for i in range(length):k = ifor j in range(k,0,-1):if arr[j]<arr[j-1]:t = arr[j]arr[j]=arr[j-1]arr[j-1]=t
arr = [4,3,0,-1]
insert_sort(arr)
print(arr)

2.冒泡排序

【算法思想】

對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最終達到完全有序。

【代碼實現】

# 冒泡排序
def bubbleSort(arr):length = len(arr)for i in range(length-1):flag = Truefor j in range(length-i-1):if arr[j]>arr[j+1]:t = arr[j]arr[j]=arr[j+1]arr[j+1]=tflag = Falseif flag:break
arr = [6,-2,0,9]
bubbleSort(arr)
print(arr)

3.選擇排序

【算法思想】

每一趟從待排序的數據元素中選擇最小（或最大）的一個元素作為首元素，直到所有元素排完為止，簡單選擇排序是不穩定排序。

【代碼實現】

def selectSort(arr):length = len(arr)for i in range(length-1):min = ifor j in range(i+1,length):if arr[min]>arr[j]:min=jif min!=i:t = arr[i]arr[i]=arr[min]arr[min]=t
arr = [6,-2,0,9]
selectSort(arr)
print(arr)

4.快速排序

【算法思想】

快速排序思想----分治法。

先從數列中取出一個數作為基準數。
分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。
再對左右區間重復第二步，直到各區間只有一個數。

每次劃分得到，樞椎的左邊比它小，右邊比它大。

【代碼實現】

方法一(通過遍歷直接得到大于pivot和小于pivot的元素)：

class Solution:def quicksort(self, array):""":type numRows: int:rtype: List[List[int]]"""if len(array)<=1:return arrayelse:pivot=array[0]small=[i for i in array[1:] if i<=pivot]big=[i for i in array[1:] if i >pivot]return self.quicksort(small)+[pivot]+self.quicksort(big)  //遞歸法，耗時

?方法二(雙指針前后移動):

def quickSort(arr,left,right):# 遞歸終止條件if left>right:returnpivot = arr[left]i = leftj = rightwhile i<j:while i<j and arr[j]>=pivot:j-=1while i<j and arr[i]<=pivot:i+=1if i<j:t = arr[i]arr[i] = arr[j]arr[j] = t# 放入樞椎arr[left] = arr[i]arr[i]=pivot# 遞歸調用左區域quickSort(arr,left,i-1)# 遞歸調用右區域quickSort(arr,i+1,right)arr = [6,-2,0,9]
quickSort(arr,0,len(arr)-1)
print(arr)

5.希爾排序

【算法思想】

該算法也被稱為：縮小增量排序。

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

【代碼實現】

# 希爾排序
def shellSort(arr):length =  len(arr)# 設置初始增量gap = length//2while gap>0:# 從第gap個元素，逐個對其所在組進行直接插入排序for i in range(gap,length):j = iwhile j-gap>=0 and arr[j]<arr[j-gap]:t = arr[j]arr[j] = arr[j-gap]arr[j-gap] = tj-=gapgap//=2
arr = [6,-2,0,9]
shellSort(arr)
print(arr)

6.堆排序

【算法思想】

堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

基本思路：

　　a.將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;

　　b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;(升序方法)

　　c.重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。

【代碼實現】

方法1：

class HeapSort:def heapSort(self, nums):length = len(nums)# 從后往前遍歷，交換堆頂與最后葉子節點，并依次調整堆，重復操作for j in range(length-1,0,-1):# 獲取堆頂元素(獲取同時，調整堆)firstNum = self.adjustHeap(nums,j+1)# 交換最后一個葉子節點與堆頂元素temp = nums[j]nums[j] = firstNumnums[0] = tempreturn nums# 調整堆(最大堆)，每次返回最大堆頂元素def adjustHeap(self,nums,length):# 最后一個非葉節點i = length//2 -1# 從最后一個非葉節點開始調整，構成最大堆while i>=0:temp = nums[i]k = 2*i+1while k<length:if k+1<length and nums[k]<nums[k+1]:k+=1if nums[k]>temp:nums[i]=nums[k]i=kelse:breakk=2*k+1nums[i] = tempi-=1return nums[0]
s = HeapSort()
nums = [8,9,7,10]
t = s.heapSort(nums)
print(t)

方法2：

def buildMaxHeap(self,arr):import mathfor i in range(math.floor(len(arr) / 2), -1, -1):self.heapify(arr, i)def heapify(self, arr, i):left = 2 * i + 1right = 2 * i + 2largest = iif left < arrLen and arr[left] > arr[largest]:largest = leftif right < arrLen and arr[right] > arr[largest]:largest = rightif largest != i:self.swap(arr, i, largest)self.heapify(arr, largest)def swap(self, arr, i, j):arr[i], arr[j] = arr[j], arr[i]def heapSort(self, arr):global arrLenarrLen = len(arr)self.buildMaxHeap(arr)for i in range(len(arr) - 1, 0, -1):self.swap(arr, 0, i)arrLen -= 1self.heapify(arr, 0)return arr

7.歸并排序

【算法思想】

歸并排序是利用歸并的思想實現的排序方法，該算法采用經典的分治策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

【代碼實現】

import math
class Solution:def mergeSort(self,arr):if (len(arr) < 2):return arrmiddle = math.floor(len(arr) / 2)left, right = arr[0:middle], arr[middle:]return self.merge(self.mergeSort(left), self.mergeSort(right))def merge(self,left, right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0));else:result.append(right.pop(0));while left:result.append(left.pop(0));while right:result.append(right.pop(0));return result

?來自于wx公眾號“光城”。

幾種排序算法代碼c++版本 (暫無堆排和希爾排序)：

#include "../stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include<functional>
#include <map>
#include <iostream>
using namespace std;void BubbleSort(vector<int> &arr){if (arr.size() <= 0)return;for (int len = arr.size() - 1; len >= 1; len--){for (int i = 0; i < len; i++){if (arr[i]>arr[i + 1])swap(arr[i], arr[i + 1]);}}
}void SelectionSort(vector<int> &arr){if (arr.size() <= 0)return;for (int i = 0; i < arr.size() - 1; i++){int min_index = i;for (int j = i + 1; j < arr.size(); j++){/*if (arr[j]<arr[j-1])    //每次左邊起始位置向前移一個，但是并不能保證一輪下來，左邊的數為最小值swap(arr[j-1], arr[j]);*/min_index = arr[min_index] < arr[j] ? min_index : j;}swap(arr[min_index],arr[i]);}
}void InsertSort(vector<int> &arr){if (arr.size() <= 0)return;for (int i = 1; i < arr.size(); i++){ //從索引1開始，前面索引0區域為插入空間for (int j = i - 1; j >= 0 && arr[j]>arr[j + 1]; j--) //--逆序（直接和插入空間最右(也即最大)的數比較，就可知是否進行插入）swap(arr[j], arr[j + 1]); //不是i,j直接比較    j--決定插入的具體位置，如（1，3，5）2
    }
}void QuickSort(vector<int> &arr,int L, int R){if (L >= R) //遞歸終止條件return;int pivot = arr[L];int i = L, j = R;while (i != j){//先從右邊找，否則會報錯while (arr[j] > pivot&&i < j)j--;while (arr[i] <= pivot&&i < j)i++;if (i < j){swap(arr[i],arr[j]);}}arr[L] = arr[i];arr[i] = pivot; //最終pivot位置為iQuickSort(arr, L, i - 1);QuickSort(arr, i + 1,R);
}//歸并：先拆分為若干子數組，通過merge()對其逐步合并排序
void Merge(vector<int> &arr, int L, int mid, int R){int i = L, j = mid + 1;vector<int> new_arr;while (i <= mid&&j <= R){if (arr[i] <= arr[j])new_arr.push_back(arr[i]),i++;elsenew_arr.push_back(arr[j]),j++;}while (i <= mid)new_arr.push_back(arr[i]), i++;while (j <= R)new_arr.push_back(arr[j]), j++;for (int k = L, t = 0; k <= R; k++, t++) //把值復制回原arrarr[k] = new_arr[t];
}void MergeSort(vector<int> &arr, int L, int R){if (L >= R)return;else{int mid = (L + R) / 2;MergeSort(arr, L, mid);MergeSort(arr, mid + 1, R);Merge(arr, L, mid, R);}
}int main(void){vector<int> array = {2, 1, 3, 5, 2, 6, 9, 2, 7 };//BubbleSort(array);//SelectionSort(array);//InsertSort(array);//QuickSort(array, 0, array.size() - 1);MergeSort(array, 0, array.size() - 1);vector<int> vec = array;vector <int>::iterator it;for (it = vec.begin(); it != vec.end();it++)cout << *it << endl;getchar();return 0;
}