1.03——排序

#include
using namespace std;
int arry[10]={1,3,7,9,5,2,8,4,6,10};
int arry2[10];

// 用于将有序数组重新还原
void Initialize()
{
    for (int i = 0; i < 10; i++)
        arry2[i]=arry[i];
}
// 用于输出
void Print()
{
    for (int i = 0; i < 10; i++)
    {
        cout<
    Initialize();
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 9;j++)
        {
            if (arry2[j]>arry2[j+1])
            {
                swap(arry2[j],arry2[j+1]);
            }
        }       
    }
    Print();
}
//**************************
//     选择排序
//   时间复杂度O(n^2)
//   同样用了双重循环
//**************************
void SelectionSort()
{
    Initialize();
    for (int i = 0; i < 10; i++)
    {
        int MinSub=i;
        int min=arry2[i];
        // 选择出最小的，与第i位交换
        for (int j = i; j < 10; j++)
        {
          if(arry2[j]
              min=arry2[j];
              MinSub=j;
          }
        }
        swap(arry2[i],arry2[MinSub]);
    }
    Print();
}
//**************************
//     插入排序
//   时间复杂度O(N)~O(N^2)
//**************************
void InsertionSort()
{
    Initialize();
    if (arry2[0]>arry2[1])
    {
        swap(arry2[0],arry2[1]);
    }
    // 不断将每个数插入到合适的位置，即num-1
        int j=i;
        while (arry2[j-1]>arry2[j]&&j>=1)
        {
            swap(arry2[j],arry2[j-1]);   
            j--;
        }
    }
    Print();
    
}
//**************************
//     Shell排序
//   时间复杂度O(n^1.5)
//**************************
void ShellSort()
{
    Initialize();
    int len = 10;
    int grp;		

    // 计算被分成多少组
    // grp每次循环完除二，获得二次的组数，5，2，1
    for (grp = len / 2; grp > 0; grp = grp / 2)
    {
        // 在内部对每一组进行选择排序
        for (int i = grp; i < len; i++) {
            int cur = arry2[i];	// 先空出第二个数的位置
            int j = 0;

            // 根据增量往前比较，小的在前，大的在后
            for (j = i - grp; j >= 0 && arry2[j] > cur; j = j - grp) {
                arry2[j + grp] = arry2[j];	// 符合条件将前面的数据移动到空出的位置
            }
            arry2[j + grp] = cur;	// 最后将待插入数据cur插入到前面空出的位置
        }
    }
    Print();
}

int main()
{
    BubblingSort();  
    SelectionSort(); 
    InsertionSort();
    ShellSort();
}

希尔排序