八大排序算法(6/6)

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

（a）一趟排序的过程：
初 始 关 键 字 : (49) 38 65 97 76 13 27 49
进 行 1 次 交 换: 27 38 65 97 76 13 (49) 49
进 行 2 次 交 换: 27 38 (49) 97 76 13 65 49
迸 行 3 次 交 换: 27 38 13 97 76 (49) 65 49
进 行 4 次 交 换: 27 38 13 (49) 76 97 65 49

算法实现:

int Partition(vector<int> &a, int low, int high) {
    int pivotKey = a[low]; // 这里pivotKey记录的一定是值，不能是下标，因为下标的值可能会换while (low < high) {
        while (low < high && a[high] >= pivotKey) high--;
        swap(a[high], a[low]);
        while (low < high && a[low] <= pivotKey) low++;
        swap(a[high], a[low]);
    }
    return low;
}
void QuickSort(vector<int> &a, int low, int high) {
    if (low < high) {
        int pivotLoc = Partition(a, low, high);
        QuickSort(a, low, pivotLoc - 1);
        QuickSort(a, pivotLoc + 1, high);
    }
}

---

7. 归并排序（Merge Sort） ( 稳定的 O(nlogn) )

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法实现：

// 7. 归并排序//将二个有序数列a[first...mid]和a[mid...last]合并。void MergeArray(vector<int> &array, int low, int mid, int high)
{
    int i = low; // i是第一段序列的下标int j = mid + 1; // j是第二段序列的下标int k = 0; // k是临时存放合并序列的下标vector<int> tmp(high - low + 1); // array2是临时合并序列// 扫描第一段和第二段序列，直到有一个扫描结束while (i <= mid && j <= high) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描if (array[i] <= array[j]) {
            tmp[k++] = array[i++];
        } else {
            tmp[k++] = array[j++];
        }
    }
    // 若第一段序列还没扫描完，将其全部复制到合并序列while (i <= mid) {
        tmp[k++] = array[i++];
    }
    // 若第二段序列还没扫描完，将其全部复制到合并序列while (j <= high) {
        tmp[k++] = array[j++];
    }
    // 将合并序列复制到原始序列中for (i = 0; i < k; i++)
        array[low + i] = tmp[i];
}
void MergeSort(vector<int> &a, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);    //左边有序
        MergeSort(a, mid + 1, high); //右边有序
        MergeArray(a, low, mid, high); //再将二个有序数列合并
    }
}

8. 桶排序/基数排序(Radix Sort) ( 稳定的 O(n) )

基本思想：

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（O（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

算法实现：

// 8. 桶排序//找到num的从低到高的第pos位的数据int GetNumInPos(int num, int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}
#define RADIXNUM 10   // 基数（桶的个数）#define KEYNUM 10     // 关键字个数，这里为最大整数的位数void RadixSort(vector<int> &a)
{
    int n = a.size();
    vector<vector<int> > bucket(RADIXNUM, vector<int>(n)); // 分配桶空间for (int pos = 1; pos <= KEYNUM; pos++)    //从个位到最高位
    {
        for (int i = 0; i < n; i++)    //分配过程
        {
            int num = GetNumInPos(a[i], pos);
            int index = ++bucket[num][0];
            bucket[num][index] = a[i];
        }

        for (int i = 0, j = 0; i < RADIXNUM; i++)   //收集
        {
            for (int k = 1; k <= bucket[i][0]; k++)
                a[j++] = bucket[i][k];
            bucket[i][0] = 0;    //复位
        }
    }
}

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了 八大排序算法，包括了方面的内容，希望对其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。

本文网址链接：http://www.codes51.com/article/detail_2156476_6.html