【数据结构与算法】七种常见排序算法

梦里梦外; 2022-01-22 04:53 230阅读 0赞

### 排序算法 ###

*  目录
 *   *  冒泡排序
     *  简单选择排序
     *  直接插入排序
     *  希尔排序
     *  堆排序
     *  归并排序
     *  快速排序
     *  时间复杂度、空间复杂度和稳定性总结

总结《大话数据结构》，本文相关代码均由C++编写。

# 目录 #

## 冒泡排序 ##

void bubblesort(int a[], int num){
 	for (int i = 0; i < num; i++){
 		for (int j = num - 1; j >= i+1; j--){
 			if (a[j] < a[j - 1])
 				swap(a[j], a[j - 1]);
 		}
 	}
 }

## 简单选择排序 ##

void selectedsort(int a[], int num){
 	for (int i = 0; i < num; i++){
 		int min = i;
 		for (int j = i+1; j <num; j++){
 			if (a[j] < a[min])
 				min = j;
 		}
 		if (i != min){
 			swap(a[i], a[min]);
 		}
 	}
 }

## 直接插入排序 ##

void insertsort(int a[], int num){
 	for (int i = 1; i < num; i++){
 		int temp = a[i];
 		int j;
 		for (j= i-1; a[j]>temp; j--){
 			a[j + 1] = a[j];
 		}
 		a[j+1] = temp;
 	}
 }

## 希尔排序 ##

void shellsort(int a[], int n){
 	int i, j;
 	int jump = n;
 	do{
 		jump = jump / 3+1;
 		for (i = jump; i<n; i++){//与直接插入不同的是，这边从gap开始，不是gap+1；
 			if (a[i]<a[i - jump]){
 				int temp = a[i];
 				for (j = i - jump; a[j]>temp; j -= jump){
 					a[j + jump] = a[j];
 				}
 				a[j + jump] = temp;
 			}
 		}
 	} while (jump > 1);
 }

## 堆排序 ##

void adjust_heap(int* a, int node, int size)
 {
 	int left = 2 * node + 1;
 	int right = 2 * node + 2;
 	int max = node;
 	if (left < size && a[left] > a[max])
 		max = left;
 	if(right < size && a[right] > a[max])
 		max = right;
 	if (max != node)
 	{
 		swap(a[max], a[node]);
 		adjust_heap(a, max, size);
 	}
 }
 
 void heap_sort(int* a, int len)
 {
 	for (int i = len / 2 - 1; i >= 0; --i)
 		adjust_heap(a, i, len);
 
 	for (int i = len - 1; i >= 0; i--)
 	{
 		swap(a[0], a[i]); // 将当前最大的放置到数组末尾
 		adjust_heap(a, 0, i); // 将未完成排序的部分继续进行堆排序
 	}
 }

## 归并排序 ##

void merge(int* a, int start, int mid, int end)
 {
 	int *tmp = new int[end - start + 1]; // tmp是汇总2个有序区的临时区域
 	int i = start; // 第1个有序区的索引
 	int j = mid + 1; // 第2个有序区的索引
 	int k = 0; // 临时区域的索引
 
 	while (i <= mid && j <= end)
 	{
 		if (a[i] <= a[j])
 			tmp[k++] = a[i++];
 		else
 			tmp[k++] = a[j++];
 	}
 
 	while (i <= mid)
 		tmp[k++] = a[i++];
 
 	while (j <= end)
 		tmp[k++] = a[j++];
 
 	// 将排序后的元素，全部都整合到数组a中。
 	for (i = 0; i < k; i++)
 		a[start + i] = tmp[i];
 
 	delete[] tmp;
 }
 
 void mergeSortUp2Down(int* a, int start, int end)
 {
 	if (a == NULL || start >= end)
 		return;
 
 	int mid = (end + start) / 2;
 	mergeSortUp2Down(a, start, mid); // 递归排序a[start...mid]
 	mergeSortUp2Down(a, mid + 1, end); // 递归排序a[mid+1...end]
 	merge(a, start, mid, end);
 }

## 快速排序 ##

int Partition(int a[], int i, int j){
 	int temp = a[i];
 	while (i < j){
 		while (i<j&& a[j]>=temp){
 			j--;
 		}
 		swap(a[i], a[j]);
 		while (i < j&& a[i] <= temp){
 			i++;
 		}
 		swap(a[i], a[j]);
 	}
 	return i;//这里不管是返回i还是j都是一样的，因为最后会相等
 }
 void quicksort(int a[], int low, int high){
 	if (low<high){
 		int q = Partition(a, low, high);
 		quicksort(a, low, q - 1);
 		quicksort(a, q + 1, high);
 	}
 }

## 时间复杂度、空间复杂度和稳定性总结 ##

<table> 
 <thead> 
 <tr> 
 <th align="center">排序方法</th> 
 <th align="center">平均情况</th> 
 <th align="center">最好情况</th> 
 <th align="center">最坏情况</th> 
 <th align="center">辅助空间</th> 
 <th align="center">稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">冒泡排序</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(n)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(1)</td> 
 <td align="center">稳定</td> 
 </tr> 
 <tr> 
 <td align="center">简单选择排序</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(1)</td> 
 <td align="center">稳定</td> 
 </tr> 
 <tr> 
 <td align="center">直接插入排序</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(n)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(1)</td> 
 <td align="center">稳定</td> 
 </tr> 
 <tr> 
 <td align="center">希尔排序</td> 
 <td align="center">O(nlogn)~O( n 2 n^{2} n2)</td> 
 <td align="center">O(( n 1.5 n^{1.5} n1.5)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(1)</td> 
 <td align="center">不稳定</td> 
 </tr> 
 <tr> 
 <td align="center">堆排序</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(1)</td> 
 <td align="center">不稳定</td> 
 </tr> 
 <tr> 
 <td align="center">归并排序</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(n)</td> 
 <td align="center">稳定</td> 
 </tr> 
 <tr> 
 <td align="center">快速排序</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O(nlogn)</td> 
 <td align="center">O( n 2 n^{2} n2)</td> 
 <td align="center">O(nlogn)~O( n 2 n^{2} n2)</td> 
 <td align="center">不稳定</td> 
 </tr> 
 </tbody> 
</table>