排序

基於插入的排序:

  • 直接插入排序算法
  • shell(希爾)排序
    基於交換的排序:
  • 冒泡排序
  • 快速排序
    基於選擇的排序:
  • 簡單選擇排序
  • 堆排序
    其他的排序:
  • 歸併排序
  • 基於統計的排序

直接插入排序

直接插入排序優化出兩個算法

  • 折半插入排序
  • 2路插入排序

直接插入排序:

  • 在添加新的數據時,我們使用順序查找的方式找到其要插入的位置,將其插入
  • 性質
  • 時間複雜度: 手撕十大排序算法（一）_#算法
  • 穩定排序
  • 就地排序
  • 內部排序

折半插入排序

  • 在直接插入排序中的順序查找換成折半查找(二分查找)
  • 優化後和沒優化基本沒有多少分別

二路插入排序

  • 新建一個和原數組相同大小的循環數組,然後再把元素依然插進去,可以節省一點交換元素的時間
  • 但優化後和沒優化基本沒有多少分別
void straight_insert_sort()//直接插入排序
{
	int i, j, x;
	for (i = 0; i < n; i++)
	{
		x = arr[i];
		for (j = 0; j < i; j++)
			if (arr[j] > arr[i])
				break;
		for (int z = i; z > j; z--)
			arr[z] = arr[z - 1];
		arr[j] = x;
	}
}

shell(希爾)排序

希爾排序又叫縮小增量排序

理論基礎

  • 插入排序在處理基本有序的數組時，效率非常高，接近 手撕十大排序算法（一）_數組_02。
  • 通過將數組按大增量分組進行插入排序，可以快速地讓距離較遠的元素到達其大致正確的位置，從而使整個數組宏觀上變得“基本有序”。
  • 隨着增量逐漸縮小，數組的有序程度越來越高，直到最後增量為1時，進行一次標準的直接插入排序，此時由於數組已基本有序，排序效率很高

定義: 在直接插入排序算法的基礎上,對待排序的數組進行分組,先對每一組進行排序,然後不斷縮小組數,不斷排序,直到縮小到為1組

如何分組

  • 比如有9個數可以分成三組(增量), 分成[1,4,7],[2,5,8],[3,6,9]
  • 增量的選擇: 不同的增量的選擇, 會使得希爾排序有不同的時間複雜度, 以下給出一個可能的增量方法
  • 對n個數據進行排序: n/2->n/4->n/8->…->1

性質

  • 時間複雜度
  • 不同的增量的選擇有不同的時間複雜度
  • 不穩定排序
  • 就地排序
  • 內部排序
void shell_sort()
{
	int x,j;
	for (int k = n/2; k >= 1; k /= 2)
	{
		for (int i = k ; i < n; i++)
		{
			x = arr[i];
			for (j = i; j >= k; j -= k)
			{
				if (arr[j-k] < x)
					break;
				arr[j] = arr[j - k];
			}
			arr[j] = x;
		}
	}
}

冒泡排序

冒泡排序: 通過不斷的比較兩個相鄰的元素,若這兩個元素是亂序的,則交換位置,從而實現每趟都把最大的數據交換到最後面

性質

  • 時間複雜度: 手撕十大排序算法（一）_#算法
  • 穩定排序
  • 就地排序
  • 內部排序
void bubble_sort()
{
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

快速排序

快速排序: 分治法, 把一個相對無序的數組, 分為兩個相對有序的數組, 那麼分出來的兩個相對有序的數組再分別運行相同的操作(即把它看做一個相對無序的數組進行處理)

  • 首先選定一個基準數x(比較的標準),把比基準數x小的數據放在x前面,把比基準數x大的數據放在後面, 排好一趟之後,x把序列分成了兩部分,這兩部分可還都是亂序,再分別對這兩部分進行快速排序

性質:

  • 時間複雜度: 手撕十大排序算法（一）_i++_04
  • 就地排序
  • 不穩定排序
  • 內部排序
void quick_sort(int arr[],int l, int r)
{
	if (l >= r)
		return;
 
	int x = arr[l+r>>1], i = l - 1, j = r + 1; 
	while (i < j)
	{
		do i++; while (arr[i] < x);
		do j--; while (arr[j] > x);
		if (i < j) swap(arr[i], arr[j]);
	}

	quick_sort(arr,l, j), quick_sort(arr,j + 1, r);
}

簡單選擇排序

簡單選擇排序: 每次從待排序區中,選擇一個最小的數,放在待排序區的第一個位置,從而實現升序排列

性質

  • 時間複雜度: 手撕十大排序算法（一）_#算法
  • 不穩定排序
  • 就地排序
  • 內部排序
void select_sort()
{
	for (int i = 0; i < n - 1; i++)
	{
		int pos = i;
		for (int j = i; j < n; j++)
			if (a[pos] > a[j])
				 pos = j;
		swap(a[i], a[pos]);
	}
}

堆排序

堆排序只是對簡單選擇排序的一個優化,找待排序區的最小一個數的時間複雜度從O(n)到O(log n) , 重點是堆的概念(上一篇有説)

#include <iostream>
using namespace std;

int a[105];

void down_adjust(int a[], int i, int n)
{
	int father = i, child = 2 * i;
	while (child <= n)
	{
		if (child + 1 <= n && a[child] > a[child + 1])
			child = child + 1;
		if (a[father] <= a[child])
			return;
		else
		{
			swap(a[father], a[child]);
			father = child;
			child = father * 2;
		}
	}
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = n / 2; i >= 1; i--)
		down_adjust(a, i, n);

	for (int i = 1,j=n; i <= n; i++,j--)
	{
		cout << a[1] << " ";
		a[1] = a[j];
		down_adjust(a, 1, j-1);
	}
	return 0;
}

歸併排序

思路: 分治法, 把兩個有序的數組合併為一個有序的數組

  • 先將所有記錄完全分開,然後兩兩合併,在合併的過程中將其排好序,最終能夠得到一個完整的有序表

性質:

  • 時間複雜度: 手撕十大排序算法（一）_#算法_06
  • 非就地排序
  • 穩定排序
void merge_sort(int a[], int l, int r)
{
	if (l >= r)return;
	int middle = l + (r - l) / 2;
	merge_sort(a, l, middle), merge_sort(a, middle + 1, r);

	int i = l, j = middle + 1, k = 0;
	while (i <= middle && j <= r)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	while (i <= middle)temp[k++] = a[i++];
	while (j <= r)temp[k++] = a[j++];

	for (int i = l, j = 0; i <= r; i++, j++)
		a[i] = temp[j];
}

基於統計的排序

  • 計數排序: 統計每個數出現的次數,然後直接按次數輸出
  • 桶排序: 把數放在桶中,然後再對每一個桶進行排序
  • 基數排序: 和桶排序差不多,但對每一個位數進行一次排序,排序一定要穩定