比较排序算法笔记

「爱情、让人受尽委屈。」 2022-09-18 01:51 180阅读 0赞

> 好几天没看《算法导论》，今天看了一天的排序算法，印象第一的是基数算法，因为居然违反我的一个常识，它采用的是最低有效位进行排序的。

插入排序、归并排序、堆排序、快速排序，这些都是比较排序算法：它们都是通过对元素进行比较操作来确定输入数组的有序次序，这些算法可以用决策树模型分析，可以证明任意比较排序算法排序n个元素的最坏情况运行时间的下界为Omega（nlgn），其中堆排序和归并排序是渐进最优的比较排序算法。

<table style="border-collapse:collapse; width:457.0000pt; padding:0.7500pt 0.7500pt 0.7500pt 0.7500pt"> 
 <tbody> 
 <tr style="height:22.8500pt"> 
 <td style="width:150.85pt; padding:0.75pt; border:0.75pt outset rgb(0,0,0)"> 算法 </td> 
 <td style="width:150.8pt; padding:0.75pt; border-style:outset outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-top-width:0.75pt; border-top-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 最坏情况运行时间 </td> 
 <td style="width:155.35pt; padding:0.75pt; border-style:outset outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-top-width:0.75pt; border-top-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 平均情况/期望运行时间 </td> 
 </tr> 
 <tr style="height:20.3000pt"> 
 <td style="width:150.85pt; padding:0.75pt; border-left-width:0.75pt; border-style:none outset outset; border-left-color:rgb(0,0,0); border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 插入排序（原址） </td> 
 <td style="width:150.8pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（n^2） </td> 
 <td style="width:155.35pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（n^2） </td> 
 </tr> 
 <tr style="height:20.3000pt"> 
 <td style="width:150.85pt; padding:0.75pt; border-left-width:0.75pt; border-style:none outset outset; border-left-color:rgb(0,0,0); border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 归并排序 </td> 
 <td style="width:150.8pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（nlgn） </td> 
 <td style="width:155.35pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（nlgn） </td> 
 </tr> 
 <tr style="height:20.3000pt"> 
 <td style="width:150.85pt; padding:0.75pt; border-left-width:0.75pt; border-style:none outset outset; border-left-color:rgb(0,0,0); border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 堆排序（原址） </td> 
 <td style="width:150.8pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（nlgn） </td> 
 <td style="width:155.35pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> -------- </td> 
 </tr> 
 <tr style="height:22.8500pt"> 
 <td style="width:150.85pt; padding:0.75pt; border-left-width:0.75pt; border-style:none outset outset; border-left-color:rgb(0,0,0); border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> 快速排序（原址） </td> 
 <td style="width:150.8pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（n^2） </td> 
 <td style="width:155.35pt; padding:0.75pt; border-style:none outset outset none; border-right-width:0.75pt; border-right-color:rgb(0,0,0); border-bottom-width:0.75pt; border-bottom-color:rgb(0,0,0)"> Theta（nlgn）期望） </td> 
 </tr> 
 </tbody> 
</table>

## 堆排序 ##

堆排序的时间复杂度和归并排序一样，都是O(nlgn)，另外它具有插入排序的空间原址性优点，即任何时候都只需要常数个额外的空间元素存储临时数据。

堆排序中主要是引入了一种称为“堆”的数据结构来进行信息管理。这里的（二叉）堆可以看作是一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素，如图1所示。

![SouthEast][]

二叉堆可以分为两种形式：最大堆和最小堆。因为在堆排序中应用的是最大堆，所以这里只说最大堆，最大堆中是指除根以外的所有结点i都要满足： A\[PARENT\[i\]\]>=A\[i\]，即某个结点的值至多与其父节点一样大。

**两个性质：**

1.  一个包含n个元素的堆可以看着一颗完全二叉树，那么该堆的高度是O(lgn)，而且堆结构上的一些基本操作的运行时间至多与树的高度成正比，即时间复杂度O(lgn);
2.  当用数组表示存储n个元素的堆时，叶结点下标分别是\[n/2\]+1,\[n/2\]+2,…，n。

**伪代码：**

HEAPSORT(A)
    　　BULID-HEAP(A)
    　　For  i = A.length  downto  2
    　　exchange A[1] with A[i]
    　　length-size=A.length-size-1
        HEAPIFY(A,1)

下面分别解析上面代码调用的子过程

这个子过程是维护最大堆，被不断的调用。

![SouthEast 1][]

这个子过程是采用自底向上建堆的过程，里面用到了上文的性质2。

![SouthEast 2][]

具体代码实现过程：

#include <cstdio>
 #include <cstdlib>
 #include <cmath>
 using namespace std;
 
 int parent(int);
 int left(int);
 int right(int);
 void Max_Heapify(int [], int, int);
 void Build_Max_Heap(int [], int);
 void print(int [], int);
 void HeapSort(int [], int);
 
 /*父結點*/
 int parent(int i)
 {
 return (int)floor((i - 1) / 2);
 }
 
 /*左子結點*/
 int left(int i)
 {
 return (2 * i + 1);
 }
 
 /*右子結點*/
 int right(int i)
 {
 return (2 * i + 2);
 }
 
 /*單一子結點最大堆積樹調整*/
 void Max_Heapify(int A[], int i, int heap_size)
 {
 int l = left(i);
 int r = right(i);
 int largest;
 int temp;
 if(l < heap_size && A[l] > A[i])
 {
 largest = l;
 }
 else
 {
 largest = i;
 }
 if(r < heap_size && A[r] > A[largest])
 {
 largest = r;
 }
 if(largest != i)
 {
 temp = A[i];
 A[i] = A[largest];
 A[largest] = temp;
 Max_Heapify(A, largest, heap_size);
 }
 }
 
 /*建立最大堆積樹*/
 void Build_Max_Heap(int A[]，int heap_size)
 {
 for(int i = (heap_size-2)/2; i >= 0; i--)
 {
 Max_Heapify(A, i, heap_size);
 }
 }
 
 /*印出樹狀結構*/
 void print(int A[]， int heap_size)
 {
 for(int i = 0; i < heap_size;i++)
 {
 printf("%d ", A[i]);
 }
 printf("\n");
 }
 
 /*堆積排序程序碼*/
 void HeapSort(int A[], int heap_size)
 {
 Build_Max_Heap(A, heap_size);
 int temp;
 for(int i = heap_size - 1; i >= 0; i--)
 {
 temp = A[0];
 A[0] = A[i];
 A[i] = temp;
 Max_Heapify(A, 0, i);
 }
 print(A, heap_size);
 }
 
 /*輸入資料並做堆積排序*/
 int main(int argc, char* argv[])
 {
 const int heap_size = 13;
 int A[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
 HeapSort(A, heap_size);
 system("pause");
 return 0;
 }

另一个代码：

#include <iostream>
 using namespace std;
 /*
 #堆排序#%
 #数组实现#%
 */
 //#筛选算法#%
 void sift(int d[], int ind, int len)
 {
 //#置i为要筛选的节点#%
 int i = ind;
 
 //#c中保存i节点的左孩子#%
 int c = i * 2 + 1; //#+1的目的就是为了解决节点从0开始而他的左孩子一直为0的问题#%
 
 while(c < len)//#未筛选到叶子节点#%
 {
 //#如果要筛选的节点既有左孩子又有右孩子并且左孩子值小于右孩子#%
 //#从二者中选出较大的并记录#%
 if(c + 1 < len && d[c] < d[c + 1])
 c++;
 //#如果要筛选的节点中的值大于左右孩子的较大者则退出#%
 if(d[i] > d[c]) break;
 else
 {
 //#交换#%
 int t = d[c];
 d[c] = d[i];
 d[i] = t;
 //
 //#重置要筛选的节点和要筛选的左孩子#%
 i = c;
 c = 2 * i + 1;
 }
 }
 
 return;
 }
 
 void heap_sort(int d[], int n)
 {
 //#初始化建堆, i从最后一个非叶子节点开始#%
 for(int i = (n - 2) / 2; i >= 0; i--)
 sift(d, i, n);
 
 for(int j = 0; j < n; j++)
 {
 //#交换#%
 int t = d[0];
 d[0] = d[n - j - 1];
 d[n - j - 1] = t;
 
 //#筛选编号为0 #%
 sift(d, 0, n - j - 1);
 
 }
 }
 
 int main()
 {
 int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#%
 
 heap_sort(a, sizeof(a) / sizeof(*a));
 
 for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
 {
 cout << a[i] << ' ';
 }
 cout << endl;
 return 0;
 }

## **快速排序** ##

上面的堆排序是一个优秀的算法，但是在实际应用中，应用更多的却是快速 排序。快速排序算法的最坏情况时间复杂度为O(n^2)，虽然最坏情况的时间复杂度很差，但是它的平均性能却非常好，它的期望时间复杂度是O(nlgn)，而且O(nlgn)中隐含的常数因子非常小。另外它还能进行原址排序，在虚拟环境下也能很好地工作。快速排序同归并排序一样，都是基于分治思想的，对一个典型的子数组A\[p..r\]进行快速排序的三步分治过程如下：

![SouthEast 3][]

伪代码：

QUICKSORT(A,p,r)
 　　if p < r
 　　q=PARTITION(A,p,r)
 　　QUICKSORT(A,p,q-1)
 　　QUICKSORT(q+1,r)

上面算法的关键部分是PARTITION过程，它实现了对子数组的原址重排。

PARTITION(A,p,r)
 　　x=A[r]
 　　i=p-1
 　　for j=p to r-1
 　　if A[j]<=x
 　　I=i+1
 　　Exchange A[i] with A[j]
 　　Exchange A[i+1] with A[r]
 　　Return i+1

![SouthEast 4][]

具体代码实现：

#include <utility>
 using std::swap;
 
 int partition(int* array, int left, int right)
 {
 int index = left;
 int pivot = array[index]; 
 swap(array[index], array[right]);
 for (int i=left; i<right; i++)
 {
 if (array[i] > pivot) // 降序
 swap(array[index++], array[i]);
 }
 swap(array[right], array[index]);
 return index;
 }
 
 void qsort(int* array, int left, int right)
 {
 if (left >= right) 
 return;
 int index = partition(array, left, right);
 qsort(array, left, index - 1);
 qsort(array, index + 1, right);
 }

[SouthEast]: /images/20220828/32adefc957a84623b143797fe6f3b584.png
[SouthEast 1]: /images/20220828/419bb80a68e94fddbe0ad6e8742dafdd.png
[SouthEast 2]: /images/20220828/180f5367dcf14bffb5a4d37fc7ef1307.png
[SouthEast 3]: /images/20220828/6c1ac7bb0a2a40849295f0b1e0fb882a.png
[SouthEast 4]: /images/20220828/a85929099ba144a2a7d0e88ee8d65c92.png