排序算法汇总及简单实现

快来打我* 2022-06-09 09:55 221阅读 0赞

排序算是比较常用的算法之一，其种类也很多，各有特点，统一撸一遍再总结一下加深理解。以下排序统一按照由小到大顺序来排。

# 插入排序 #

插入排序就是从未排序数组中选择一个插入到排序数组的合适位置

## 1.直接插入排序 ##

void insert_sort()
    {
    	for (int i = 1; i < len; i++)
    	{//第一个已经排好
    		int j = i;
    		int temp = list[i];
    		while (j > 0 && temp < list[j - 1])
    		{//寻找插入位置
    			list[j] = list[j - 1];
    			j--;
    		}
    		list[j] = temp;
    	}
    }

直接插入排序性质：

1.对于随机排列长度为N且主键不重复的数组，平均情况插入排序需要N^2 / 4次比较以及N^2 / 4次交换；最坏情况下需要N^2 / 2次比较以及N^2 / 2次交换；最好情况下需要N - 1次比较和0次交换。时间复杂度为O(n^2)。

2.运行时间和输入有关，适用于某些类型的非随机数组。

3.对于部分有序的数组十分高效，也很适合小规模数组。

4.稳定性：稳定

## 2.二分插入排序 ##

void Binary_sort()
    {
    	for (int i = 0; i < len; i++)
    	{
    		int low = 0;
    		int high = i - 1;
    		int temp = list[i];
    		while (low <= high)
    		{//二分寻找插入位置
    			int middle = (low + high) / 2;
    			if (list[middle] < temp)
    				low = middle + 1;
    			else
    				high = middle - 1;
    		}
    		for (int j = i; j > low; j--)
    		{//移位
    			list[j] = list[j - 1];
    		}
    		list[j] = temp;
    	}
    }

## 3.希尔排序 ##

将数组按照间隔值划分，分别排好序后，再划分，整体将越来越有序

void shell_sort()
    {
    	int gap = len / 2;
    	while (gap)
    	{//gap>=1
    		for (int i = gap; i < len; i++)
    		{
    			int temp = list[i];
    			int j = i;
    			while (j >= 0 && temp < list[j - gap])
    			{
    				list[j] = list[j - gap];
    				j -= gap;
    			}
    			list[j] = temp;
    		}
    		gap = gap / 2;
    	}
    }

希尔排序性质：

1.希尔排序与直接插入排序的区别在于交换的元素不相邻，因此可以将元素交换到很远的地方。

2.希尔排序可以用于大型数组，而且数组越大优势越大。

3.运行时间达不到O(n^2)级别。  
4.稳定性：不稳定

# 选择排序 #

选择排序就是从未排序数组中选择最小的依次排列

## 1.直接选择排序 ##

void select_sort()
    {
    	for (int i = 0; i < len; i++)
    	{//选择次数
    		int k = i;
    		for (int j = len + 1; j < len; j++)
    		{//比较次数
    			if (list[k] < list[j])
    				k = j;
    		}
    		swap(i, k);
    	}
    }

直接选择排序性质：

1.对于长度为N的数组，选择排序需要大约N^2 / 2次比较和N次交换，因此算法的时间复杂度为O(n^2)。

*  (N - 1) + (N - 2) + (N - 3) + ... + 2 + 1 = N\*(N - 1) / 2 ~N^2

2.运行时间和输入无关，不论是主键全部相等的数组还是元素随机排列的数组还是一个已经有序的数组，所用的排序时间一样长。

3.数据移动是最少的，每次交换一对元素，选择排序用了N次交换，交换次数和数组的关系是线性关系。

4.稳定性：不稳定

## 2.堆排序 ##

void Heap(int current, int last)
    {//建堆
    	int child = 2 * current + 1;
    	int temp = list[current];
    	while (child <= last)
    	{
    		if (child < last && list[child] < list[child + 1])//找到最大孩子
    			child++;
    		if (temp > list[child])
    			break;
    		else
    		{
    			list[current] = list[child];
    			current = child;
    			child = 2 * current + 1;
    		}
    	}
    	list[current] = temp;
    }
    void Heap_sort()
    {
    	for (int i = (len - 2) / 2; i >= 0; i--)
    	{
    		Heap(i, len - 1);//建立大顶堆
    	}
    	for (i = len - 1; i >= 0; i--)
    	{
    		swap(0, i);//最大值与最后一位交换
    		Heap(0, i - 1);//剩余重新建堆
    	}
    }

堆排序性质：

1.唯一能够同时最优利用时间和空间的方法

2.当空间十分紧张时它很流行，但除此外应用较少，因为无法利用缓存。  
3.稳定性：不稳定

# 交换排序 #

## 1.冒泡排序 ##

void bubble_sort()
    {
    	bool flag = true;
    	for (int i = 0; i < len && flag; i++)
    	{
    		flag = false;
    		for (int j = len - 1; j > i; j--)
    		{
    			if (list[j] < list[j - 1])
    			{
    				swap(j, j - 1);
    				flag = true;
    			}
    		}
    	}
    }

## 2.快速排序 ##

void quick_sort(int low, int high)
    {
    	int i = low;
    	int j = high;
    	int val = list[low];
    	while (i < j)
    	{
    		while (i < j && list[j] >= val)
    			j--;
    		if (i < j)
    			swap(i, j);
    		while (i < j && list[i] < val)
    			i++;
    		if (i < j)
    			swap(i, j);
    	}
    	if (i != low) quick_sort(low, i - 1);
    	if (j != high) quick_sort(j + 1, high);
    }

三向切分的快速排序

void QuickSort::Quick3way(int low, int high)
    {
    	if (high <= low) return;
    	int lt = low;
    	int i = low + 1;
    	int gt = high;
    	int flag = data[low];
    	while (i <= gt)
    	{
    		int compare = data[i] - flag;
    		if (compare < 0) swap(lt++, i++);
    		else if (compare > 0) swap(i, gt--);
    		else i++;
    	}
    	Quick3way(low, lt - 1);
    	Quick3way(gt + 1, high);
    }

快速三向切分

void QuickSort::Fast3way(int low, int high)
    {
    	if (high <= low) return;//
    	int i = low, j = high+1;
        int p = low, q = high+1;
        int v = data[low];
    	while (true)
    	{
    		while ((data[++i] < v))
    			if (i == high) break;
    		while ((v < data[--j]))
    			if (j == low) break;
    
                // pointers cross
    		if (i == j && data[i] == v)
    			swap(++p, i);
    		if (i >= j) break;
    		swap(i, j);
    		if (data[i] == v) swap(++p, i);
    		if (data[j] == v) swap(--q, j);
    	}
    	i = j + 1;
    	for (int k = low; k <= p; k++)
    		swap(k, j--);
    	for (int k = high; k >= q; k--)
    		swap(k, i++);
    	Fast3way(low, j);
    	Fast3way(i, high);
    }

稳定性：不稳定

# 归并排序 #

## 1.自顶向下归并排序 ##

void merge(int a[], int first, int middle, int last, int temp[])
    {//两有序数组合并
    	int i = first;
    	int j = middle + 1;
    	int m = middle;
    	int n = last;
    	int k = 0;
    	while (i <= m && j <= n)
    	{
    		if (a[i] <= a[j])
    			temp[k++] = a[i++];
    		else
    			temp[k++] = a[j++];
    	}
    	while (i <= m)
    		temp[k++] = a[i++];
    	while (j <= n)
    		temp[k++] = a[j++];
    	for (i = 0; i < k; i++)
    	{
    		a[first + i] = temp[k];
    	}
    }
    void merge_sort(int a[], int first, int last, int temp[])
    {
    	if (first < last)
    	{
    		int middle = (first + last) / 2;
    		merge_sort(a, first, middle, temp);//左边有序
    		merge_sort(a, middle + 1, last, temp);//右边有序
    		merge(a, first, middle, last, temp);//合并
    	}
    }
    void Merge_sort(int a[], int n)
    {//开新数组，定义入口
    	int temp = new int[n];
    	merge_sort(a, 0, n - 1, temp);
    }

### 归并排序改进1 ###

对于小数组采用插入排序来加快小数组的排序速度

void Merge_Sort::mergesort(int first, int last, int *temp)
    {
    	if (first + M >= last)
    		insert_sort(first, last);
    	else if (first < last)
    	{
    		int middle = (first + last) / 2;
    		mergesort(first, middle, temp);//左边有序
    		mergesort(middle + 1, last, temp);//右边有序
    		if (data[middle] > data[middle + 1])
    			merge(first, middle, last, temp);
    	}
    	else
    		return;
    }

### 归并排序改进2 ###

增加判断条件，如果data\[mid\] 小于等于data\[mid + 1\]则认为数组有序，不需要归并，代码如上。

## 2.自底向上归并排序 ##

void Merge_Sort::mergesort_btt(int *temp)
    {
    	for (int sz = 1; sz < count; sz = sz + sz)
    	{//子数组长度
    		for (int lo = 0; lo < count - sz; lo += sz + sz)//子数组索引
    			merge(lo, lo + sz - 1, min(lo + sz + sz - 1, count - 1), temp);//最后子数组不足时取count - 1
    	}
    }
    void Merge_Sort::Mergesort_btt()
    {
    	int *temp = new int[count];
    	mergesort_btt(temp);
    	delete temp;
    }

归并排序性质：

1.最吸引人的性质为归并排序能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比。

2.主要缺点是它需要的额外空间和N成正比。  
3.稳定性：稳定

# 计数排序 #

void count_sort()
    {	
    	for (int i = 0; i < len; i++)
    	{//统计次数
    		temp[list[i]]++;
    	}
    	for (int i = 1; i < max; i++)
    	{//构建定位数组
    		temp[i] += temp[i - 1];
    	}
    	for (int i = len - 1; i >=0; i--)
    	{//在新数组中排序
    		rank[--temp[list[i]] = list[i];
    	}
    }