八大排序算法(5/6)

本篇文章主要介绍了" 八大排序算法"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下： 八大排序算法标签：算法 查找和排序1. 插入排序—直接插入排序 ( 稳定的 O(nlogn) )基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个...

//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  void MinHeapFixdown(vector<int> &a, int i, int n)  
{  
    int j, temp;  
    temp = a[i];  
    j = 2 * i + 1;  
    while (j < n)  
    {  
        if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的  
            j++;  

        if (a[j] >= temp)  
            break;  

        a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点  
        i = j;  
        j = 2 * i + 1;  
    }  
    a[i] = temp;  
}  
//在最小堆中删除数  void MinHeapDeleteNumber(vector<int> &a,int n)  
{  
    Swap(a[0], a[n - 1]);  
    MinHeapFixdown(a, 0, n - 1);  
}  

建立小顶堆

void MakeMinHeap(vector<int> &a, int n)  
{  
    for (int i = n / 2 - 1; i >= 0; i--)  
        MinHeapFixdown(a, i, n);  
} 

堆排序

// 小顶堆排序后的数组是递减的，若要递增，使用大顶堆void Minheapsort(vector<int> &a, int n)  
{   
    MakeMinHeap(a, n); 
    for (int i = n - 1; i >= 1; i--)  
    {  
        Swap(a[i], a[0]);  
        MinHeapFixdown(a, 0, i);  
    }  
}  

完整的堆排序

// 4. 堆排序void MaxHeapFixdown(vector<int> &a, int i, int n)  
{  
    int j = 2 * i + 1, temp = a[i];  
    while (j < n)  
    {  
        if (j + 1 < n && a[j + 1] > a[j]) //在左右孩子中找最大的  
            j++;  

        if (a[j] <= temp)  
            break;  

        a[i] = a[j];     //把较大的子结点往上移动,替换它的父结点  
        i = j;  
        j = 2 * i + 1;  
    }  
    a[i] = temp;  
}  
void MakeMaxHeap(vector<int> &a, int n)  
{  
    for (int i = (n-1)/2; i >= 0; i--)  
        MaxHeapFixdown(a, i, n);  
}  
void Maxheapsort(vector<int> &a, int n)  
{  
    MakeMaxHeap(a, n);  
    for (int i = n - 1; i > 0; i--)  
    {  
        swap(a[i], a[0]);  
        MaxHeapFixdown(a, 0, i);  
    }  
} 

5. 交换排序—冒泡排序（Bubble Sort） ( 稳定的 O(n2) )

基本思想:

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法实现:

void BubbleSort(vector<int> &a) {
    int n = a.size();
    for(int i = 0;ifor(int j=0;j<>1;++j){
        if(a[j] > a[j+1])
            swap(a[j],a[j+1]);
    }
}  

6. 交换排序—快速排序（Quick Sort） ( 不稳定的 O(nlogn) )

基本思想:

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：