C++实现排序的几个简单实验

实现思路：

1.直接插入排序实现的方法非常直观，就像是斗地主的时候摸牌一样，右手摸牌，左手抓牌，每摸一张就按照大小找到待插入的位置，这样左手上的牌就都是有序的了。

2.冒泡排序（Bubble sort），体现的是【交换排序】的思想，即两两比较待排序记录的关键字，若不满足要求，则交换位置，直到整个序列都满足要求为止。

3.快速排序是在冒泡排序的基础上进行的改良，由于冒泡排序只对相邻两个记录进行比较，因此每次交换只能消除一个逆序。而快速排序之所以提升了速度，就是因为它的每次交换消除了多个逆序。实现的思路是引入基准，基准通常是指待排数据的第一个元素，这里其实可以根据数据来选择不同的基准，基准的选择会涉及到一些比较复杂的算法，这里不作展开。以基准来将数据分为两个子表，左子表均小于基准而右子表均大于基准。接着对两个子表进行递归，再次用基准将其分为两部分，直到每一个子表只有一个记录时，排序完成。

4.折半插入排序，这种排序方法利用了折半查找的思想，与快速排序一样，都使用了【分治策略】，用折半查找来找到待插入数据的下表来完成排序，具体思路可以参考折半查找的实现方法。

下面给出代码实现。

#include
using namespace std;

//输出数组
void showarray(int array[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
}


//直接插入排序
void InsertSort(int array[], int size)
{
    for (int i = 1; i < size; i++)
    {
        int temp = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > temp)
        {     //向前遍历数组
            array[j + 1] = array[j];    //后移     
            j--;
        }
        array[j + 1] = temp;

        //打印每次排序结果
        showarray(array, size);
    }
}

//冒泡排序
void maopao(int array[], int size)
{
    for (int i = size-1;i>0 ;i--)
    {
        showarray(array, size); //打印每次排序的结果
        for (int j = 0;j < i;j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = 0;
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

//快速排序
int kuaisu1(int* array, int low, int high) //这里使用递归的方法
{
    int size_4 = 8;
    int temp = 0;
    temp = array[low];
    while (low < high)
    {
        while (temp <= array[high] && low < high)
        {
            high--;
        }
        if (low < high)
        {
            array[low++] = array[high];
        }
        while (temp >= array[low] && low < high)
        {
            low++;
        }
        if (low < high)
        {
            array[high--] = array[low];
        }
    }
    array[low] = temp;
    showarray(array, size_4);
    return low;
}
void kuaisu2(int* array, int low, int high)
{
    if (low < high)
    {
        int pos = kuaisu1(array, low, high);   //将子表一分为二
        kuaisu2(array, low, pos - 1);  //对左子表递归
        kuaisu2(array, pos + 1, high);   //对右子表递归
    }
}

void quick_sort(int* array, int low, int high)
{
    if (array == NULL || low >= high)
    {
    return;
    }
    kuaisu2(array, low, high);
}


int main() {
    //直接插入排序
    cout << "直接插入排序" << endl;
    int array_1[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    int size_1 = sizeof(array_1) / sizeof(int);
    showarray(array_1, size_1);    
    InsertSort(array_1, size_1);
    cout << "————————————" << endl;

    //冒泡排序
    cout << "冒泡排序" << endl;
    int array_2[] = { 49,38,65,97,49,13,27,76 };
    int size_2 = sizeof(array_2) / sizeof(int);
    maopao(array_2, size_2);
    cout << "——————————————" << endl;

    //快速排序
    cout << "快速排序" << endl;
    int array_3[] = { 49,38,65,91,49,13,27,76 };
    int size_3 = sizeof(array_3) / sizeof(int);
    showarray(array_3, size_3);
    quick_sort(array_3, 0, 7);
    system("pause");
    return 0;
}

#include        
using namespace std;
#define Maxsize 50

typedef struct
{
    int score;  //分数，即关键字
    char name[5];
    char sex[2];
}record;

typedef struct
{
    record stu[Maxsize];
    int length;
}seqlist;

//输出整个表
void showlist(seqlist a)
{
    for (int i = 0;i < a.length;i++)
    {
        cout << "学号为：" << a.stu[i].score << endl;
        cout << "名字为：" << a.stu[i].name << endl;
        cout << "性别为：" << a.stu[i].sex << endl;
    }
}


//表建立
void Create(seqlist& a)
{
    a.length = 0;
    cout << "请依次输入分数、名字、性别" << endl;
    int num = 0;
    int i = 0;
    while (true)
    {
        cout << "分数（输入为0，默认终止）：" << endl;
        cin >> num;
        if (num == 0)
        {
            break;
        }
        else
        {
            a.stu[i].score = num;
            cout << "姓名:";
            cin >> a.stu[i].name;
            cout << endl;
            cout << "性别：";
            cin >> a.stu[i].sex;
            cout << endl;
            i++;
            a.length++;
        }
    }
}

//折半插入排序
void midinsert(seqlist& a)
{
    int front, end, temp;
    for (int i = 1;i < a.length;i++)
    {
        temp = a.stu[i].score;
        front = 0;
        end = i - 1;
        while (front <= end)
        {
            int mid;
            mid = (front + end) / 2;
            if (temp < a.stu[mid].score)
            {
                end = mid - 1;
            }
            else
            {
                front = mid + 1;
            }
        }
        for (int z = i;z > front;z--)
        {
            a.stu[z].score = a.stu[z - 1].score;
        }
        a.stu[front].score = temp;
        showlist(a);
        cout << endl;
    }
}



int main()
{
    seqlist a;
    Create(a);
    cout << "输出创建后的表！" << endl;
    showlist(a);
    cout << endl;
    midinsert(a);
}