C语言实现冒泡排序，选择排序，插入排序及其移动次数

Question

1、编写main()函数测试各种排序算法的正确性；
2、针对各排序算法分别测试实验数据为：顺序、逆序、随机三种情况；
3、对以上各种实验数据的测试比较各排序算法的时间复杂度。

Answer 1

你说的排序我给你源代码，在代码里面简单的说了一下算法思想。

如果是要学习，我建议去看书和看别人的博客，明白排序的思想，

只有明白了算法的思想，才能轻易的看懂排序的代码。

我的代码都是给定好的数据，是为了方便测试。

冒泡排序：

/*****************************************************************************************
   算法：
         1、相邻两个元素进行比较，即0号元素和1号元素、1号元素和2号元素、2号元素和3号元素，依此类推。
         2、每轮比较之后，就会产生一个最值，并且这个最值总是在最后面才出现，如同鱼儿吐泡。
         3、第一轮比较之后，最值在最后面；第二轮比较之后，次最值在倒数第二个位置，依此类推。
*****************************************************************************************/
#include <io
using namespace std;
void Swap(int *elem_1, int *elem_2)
{
   int temp = *elem_1;
    *elem_1 = *elem_2;
    *elem_2 = temp;
}
void Bubble_Sort(int *array,int len)
{
    for(int i=0; i<len-1; i++)
       for(int j=0; j<len-1-i; j++)
          if(array[j] > array[j+1])
            Swap(array+j,array+j+1);
}
int main(void)
{
    int array[10]={4,9,7,0,3,1,5,8,2,6};
    Bubble_Sort(array,10);
    for(int i=0; i<10; i++)
       cout<<array[i]<<" ";
    return 0;
}

选择排序：

/*****************************************************************************************
   算法：
         1、第一轮比较：假设第一个元素是最小的；第二轮比较：假设第二个元素是最小的，依此类推。
         1、用假设的元素对数组进行遍历比较，不符合要求的记录其下标。
         2、每轮比较之后才判断假设是否成立，不成立的话，就交换数据。
*****************************************************************************************/
#include <iostream>
using namespace std;
void Swap(int *elem_1, int *elem_2)
{
   int temp = *elem_1;
    *elem_1 = *elem_2;
    *elem_2 = temp;
}
void Select_Sort(int *array,int len)
{
    for(int i=0; i<len; i++)
    {
        int min_index = i;
        for(int j=i+1; j<len; j++)
           if( array[min_index] > array[j])
             min_index = j;
        if( min_index != i )
          Swap(array+min_index,array+i);
    }
}
int main(void)
{
    int array[10]={4,9,7,0,3,1,5,8,2,6};
    Select_Sort(array,10);
    for(int i=0; i<10; i++)
       cout<<array[i]<<" ";
    cout<<endl;
    return 0;
}

插入排序：

/****************************************************************************************
   算法：
         1、将要排序的数组看成一个无序和有序数组。
         2、有序数组中腾出一个适当的位置。
         3、将无序的数组元素逐渐插入到有序数组中。
****************************************************************************************/
#include <iostream>
using namespace std;
void Insert_Sort(int *array,int len)
{
    for(int i=1; i<len; i++)
    {
        int insert_index = i,temp = array[i];
        for(; array[insert_index-1] > temp && insert_index; insert_index--)
           array[insert_index] = array[insert_index-1];
        array[insert_index] = temp;
    }
}
int main(void)
{
    int array[10]={4,9,7,0,3,1,5,8,2,6};
    Insert_Sort(array,10);
    for(int i=0; i<10; i++)
       cout<<array[i]<<" ";
    cout<<endl;
    return 0;
}

Answer 2

顺序O(n) 逆序哦O（n）随机O(n)