排序的本质就是消除序列中的逆序对，关于逆序对的介绍参考逆序对,利用贪心的思想，消除相邻两个项的逆序对，复杂度为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;
}
