排序——内部排序之交换排序排序——内部排序之交换排序

81 阅读 0 评论 54 点赞

我是靠谱客的博主能干外套，最近开发中收集的这篇文章主要介绍排序——内部排序之交换排序排序——内部排序之交换排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排序——内部排序之交换排序

排序——内部排序之交换排序
- 内部排序
- 算法练习

排序——内部排序之交换排序

内部排序

排序的一篇优秀博客

插入排序
折半插入排序
希尔排序（不稳定）
冒泡排序

void BubbleSort(ElemType A[], int n) {
    int temp = 0;
    //  标记数组是不是有序的；
    bool flag = false;
    for (int i = 0; i < n - 1; i++) {
        flag = false;
        for (int j = n - 1; j > i; j--) {
            if(A[j - 1].key > A[j].key) {
                temp = A[j - 1].key;
                A[j - 1].key = A[j].key;
                A[j].key = temp;
                flag = true;
            }
        }
        if(flag == false)
            return;
    }
}

快速排序

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int mid = Partion(A, low, high);
        QuickSort(A, low, mid - 1);
        QuickSort(A, mid + 1, high);
    }
}

int Partion(ElemType A[], int low, int high) {
    ElemType privot = A[low];  
    //  将数组的第一个元素设置成枢纽值，对数组进行划分
    while(low < high) {
        while(low < high && A[high] >= privot) --high;
        A[low] = A[high];
        while(low < high && A[low] <= privot) ++low;
        A[high] = A[low];
    }
    A[low] = privot;
    return low;
}

算法练习

线性表按顺序存储，使用最少的时间和空间将所有奇数移动到偶数的前面

void OddEvenEx(ElemType A[], int n) {
    int i = 0;
    int j = n - 1;
    while(i < j) {
        while(i < j && A[j] % 2 != 1) --j; 
        //  从后向前寻找第一个奇数
        while(i < j && A[i] % 2 != 0) ++i;
        //  从前向后寻找第一个偶数
        if (i < j) {
            Swap(A[i], A[j]);
            ++i;
            --j;
        }
    }
}

试在数组A[1…n]中寻找第k小的数。

ElemType KthLeast(ElemType A[], int k, int low, int high) {
    ElemType privot = A[low];
    int low_temp = low;
    int high_temp = high;
    while(low < high) {
        while(low < high && A[high] >= privot) --high;
        A[low] = A[high];
        while(low < high && A[low] <= privot) ++low;
        A[high] = A[low]; 
    }
    A[low] = privot;
    /*这里使用递归的方式来实现 
    if (low == k) {
        return A[low];
    } else if (low < k) {
        low = low + 1;
        high = n - 1;
    } else {
        high = low - 1;
        low = 0;
    } */
    //这里的k如果数组下表是从0开始的话，最开始的时候k需要减1
    if (low == k) {
        return A[low];
    } else if (low < k) {
        // 在后一部分继续寻找
        return KthLeast(A, k, low + 1, high_temp);
    } else {
        //  在前一部分继续寻找
        return KthLeast(A, k, low_temp, low - 1);
    }
}

2016年计算机联考真题

已知由n（n>=2）个正整数构成的集合A ，将其划分成两个不相交的子集A1和A2，元素个数分别为n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C`cpp语言描述算法，关键之处给出注释。
3）说明你所设计算法的平均时间复杂度和空间复杂度。

算法解析：这道题目是求第k大的数的一个变种.

|n1-n2|最小且|S1-S2|最大，在数组元素为奇数个的时候，|n1-n2|最小为1，那么把前n/2个最小的数放在一个数组，后面n/2+1个比较大的数放在另一个数组，这时得到的结果满足条件；数组元素为偶数个的时候，|n1-n2|最小为0，所以，第一个数组里面的数是比较小的前n/2个数，第二个数组的是后n/2个比较大的数

void ArrPartion(ElemType A[], int low, int high, int k) {
    ElemType privot = A[low];
    int low_temp = low;
    int high_temp = high;
    while(low < high) {
        while(low < high && A[high] > privot) --high;
        A[low] = A[high];
        while(low < high && A[low] < privot) ++low;
        A[high] = A[low];
    }
    A[low] = privot;

    if (low == k) {
        return;
    } else if (low < k) {
        ArrPartion(A, low_temp, low - 1, k);
    } else {
        ArrPartion(A, low + 1, high_temp, k);
    }
}

荷兰国旗难题

现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

**算法思想：**对线性表从前往后进行扫描，将红色的条块放到前面，蓝色对的条块放到后面，白色的条块自然也就在中间的位置，故而需要三个指针，begin和end分别指向数组的头部和尾部，current指针从前往后扫描，如果遇到红色就和头部进行交换，如果遇到蓝色则和尾部交换。

算法实现如下所示：

#include<iostream>
#include<algorithm>
using namespace std;

typedef enum{RED, WHITE, BLUE} color;
void Holland_Partion(color arr[], int n) {
    int begin = 0;
    int end = n - 1;
    int current = begin;
    color temp;
    while(current <= end) {
        switch(arr[current]){
            case RED:
                temp = arr[begin];
                arr[begin] = arr[current];
                arr[current] = temp;
                begin++;
                current++;
                break;
            case WHITE:
                current++;
                break;
            case BLUE:
                temp = arr[end];
                arr[end] = arr[current];
                arr[current] = temp;
                end--;
                //  current没有++，因为担心交换后current指向的仍为BLUE
        }
    }
}

int main() {
    color arr[12];
    for(int i = 0; i < 12; i+=3) {
        arr[i] = WHITE;
        arr[i + 1] = BLUE;
        arr[i + 2] = RED;
    }
    for(int i = 0; i < 12; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    Holland_Partion(arr, 12);
    for(int i = 0; i < 12; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}