数据结构--排序算法以及C++实现

Love The Way You Lie 2022-04-08 12:11 135阅读 0赞

## 数据结构排序算法 ##

### 文章目录 ###

*   *  数据结构排序算法
     *   *  插入排序
         *  选择排序
         *  冒号排序
         *  归并排序

### 插入排序 ###

**插入排序**：(Straight Insertion Sort)抓扑克牌，做一遍遍历，向之前的有序序列中插入元素

*  时间复杂度：  o ( n 2 ) o(n^2) o(n2)
 *  空间复杂度： o ( n ) o(n) o(n)
 *  稳定性： 稳定

**希尔排序**：(Shell’s Sort) “缩小增量排序”，将相间隔某个增量的记录组成一个子序列。对每个子序列进行排序，逐渐缩小增量，增加子序列长度并排序。直到增量为一，进行一次插入排序即可。  
希尔排序是对插入排序的改进，将整体分割为许多子序列，使得交换位跨度大，跳过许多中间值。

* 时间复杂度： o ( n l o g n ) < T ( n ) < o ( n 2 ) o(nlogn) < T(n) < o(n^2) o(nlogn)<T(n)<o(n2)
 * 空间复杂度： o ( 1 ) o(1) o(1)
 * 稳定性： 不稳定

### 选择排序 ###

**选择排序**：(Selection Sort) 在每趟循环中找到最小（大）值，并与第i个记录交换

*  时间复杂度：  o ( n 2 ) o(n^2) o(n2)
 *  空间复杂度： o ( 1 ) o(1) o(1)
 *  稳定性：稳定（从后向前找最小可能不稳定）

**堆排序**：(Heap Sort)

1.  完全二叉树
2.  构建堆
3.  整理堆（大根堆、小根堆）排序  
    大根堆每次选择最大的，小根堆每次选择最小的。  
    *堆顶元素与最后一个元素交换* 原理同选择排序

#include <iostream>
 #include <algorithm>
 using namespace std;
 
 void max_heapify(int arr[], int start, int end) { 
 //建立父节点指标和子节点指标
 int dad = start;
 int son = dad * 2 + 1;
 while (son <= end) { //若子节点指标在范围内才做比较
 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
 son++;
 if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
 return;
 else { //否则交换父子内容再继续子节点和孙节点比较
 swap(arr[dad], arr[son]); // c++内置swap函数
 dad = son;
 son = dad * 2 + 1;
 }
 }
 }
 
 void heap_sort(int arr[], int len) { 
 //初始化，i从最後一个父节点开始调整
 for (int i = len / 2 - 1; i >= 0; i--)
 max_heapify(arr, i, len - 1);
 //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
 for (int i = len - 1; i > 0; i--) { 
 swap(arr[0], arr[i]);
 max_heapify(arr, 0, i - 1);
 }
 }
 
 int main() { 
 int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
 int len = (int) sizeof(arr) / sizeof(*arr);
 heap_sort(arr, len);
 for (int i = 0; i < len; i++)
 cout << arr[i] << ' ';
 cout << endl;
 return 0;
 }

*  时间复杂度：  o ( n l o g n ) o(nlogn) o(nlogn) (树深为 o ( l o g n ) o(logn) o(logn))
 *  空间复杂度： o ( 1 ) o(1) o(1)
 *  稳定性： 不稳定

### 冒号排序 ###

**冒号排序**：(Buddle Sort) 冒泡原理排即可

**快速排序**： (quick Sort) 任选一个作为记录，前后两个游标，从前向后找比枢轴小的，从后向前找比枢轴大的。直至左右游标相等为止。代码如下：

void quickSort(int *a, int low, int high){ 
 	//递归结束条件，传参变量 
 	if(low >= high) return ;
 	int i = low, j = high;
 	a[0] = a[i];// 哨兵
 	while(i < j){ 
 		while(i < j && a[j] >= a[0]) j--;
 		a[i] = a[j];
 		while(i < j && a[i] <= a[0]) i++;
 		a[j] = a[i];
 	}
 	a[i] = a[0];
 	quickSort(a,low,i-1);
 	quickSort(a,i+1,high);
 }

<table> 
 <thead> 
 <tr> 
 <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 l o g n ) o(nlogn) o(nlogn)</td> 
 <td align="center"> o ( n 2 ) o(n^2) o(n2)</td> 
 </tr> 
 <tr> 
 <td align="center">空间</td> 
 <td align="center"> o ( l o g 2 n ) o(log_2n) o(log2n)</td> 
 <td align="center"> o ( n ) o(n) o(n)</td> 
 </tr> 
 </tbody> 
</table>

### 归并排序 ###

**归并排序** ：(Merging Sort) 将两个有序表归并成一个新的有序表，初始将每个元素看做一个有序表。

*  时间复杂度：  o ( n l o g n ) o(nlogn) o(nlogn)
 *  空间复杂度：  o ( n ) o(n) o(n)