基于贪心策略的排序算法

排序的本质就是消除序列中的逆序对，关于逆序对的介绍参考逆序对,利用贪心的思想，消除相邻两个项的逆序对，复杂度为O(n^2),代码如下：

void greedy_sort(int a[],int n = 10){
    for(int i = 1;i < n;){
        if(i < 1 || a[i-1] <= a[i])
            i++;
        else{
            swap(a[i-1],a[i]); i--;
        }
    }
}

改进版

记录下最右侧逆序对位置记录，复杂度仍旧为O(n^2)，但极大减少光标移动数，优化了接近一半。
代码如下：

void greedy_sort(int a[],int n = 10){
    int flag = 1 ;//跳转的标记;
    for(int i = 1;i < n;){
        flag = i;
        while(a[i] < a[i-1] && 0 < i){
            swap(a[i],a[i-1]);
            i--;
        }
            i = flag;
            i++;
            flag = i;
    }
}

完整代码：

#include "iostream"
using namespace std;

int a[] = {10,5,17,65,21,48,10,35,85,45};

void swap(int & x,int & b){ //引用变量
    int temp;
    temp = x;
    x = b;
    b = temp;
}


void greedy_sort(int a[],int n = 10){
    for(int i = 1;i < n;){
        if(i < 1 || a[i-1] <= a[i])
            i++;
        else{
            swap(a[i-1],a[i]); i--;
        }
    }
}
void greedy_sort1(int a[],int n = 10){
    int flag = 1 ;//跳转的标记;
    for(int i = 1;i < n;){
        flag = i;
        while(a[i] < a[i-1] && 0 < i){
            swap(a[i],a[i-1]);
            i--;
        }
            i = flag;
            i++;
            flag = i;
    }
}

int main(int argc, char const *argv[])
{
    greedy_sort(a);
    i = 0;
    while(i < 10){
        cout<<a[i]<<" ";
        i++;
    }
    return 0;
}