----------------

排序

----------------

冒泡排序思想：

“比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。”

 

 

选择排序思想：

“从头至尾扫描序列,找出最小的一个元素,和第一个元素交换,接着从剩下的元素中继续这种选择和交换方式,最终得到一个有序序列。

 

直接插入排序思想：

“直接插入排序的基本操作是将一个记录插到已排队好的有序表中，从而得到一个新的，记录增1的有序表。（第一个有序表可认为是第一个元素）“

 

 

 

希尔排序思想：

  先取一个小于n的整数d ₁作为第一个增量，把文件的全部记录分成d ₁个组。所有距离为d _l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d ₂<d ₁重复上述的分组和排序，直至所取的增量d _t=1(d _t<d _t-l<…<d ₂<d ₁)，即所有记录放在同一组中进行直接插入排序为止。
    　该方法实质上是一种分组插入方法。

 

堆排序思想：

待实现

 

归并排序思想：

待实现

 

快速排序思想;

 

 

测试主函数

#include <stdio.h>
#include<stdlib.h>
#include <time.h>
#include "sort.h"


int main()
{
    ArrayList numlist;
    PtArrayList pt_arraylist;
    pt_arraylist = &numlist;
    while(True){
        Init_Data(pt_arraylist);
        show((char *)"排序前 ", pt_arraylist);
        
//        BubbleSort_Low(pt_arraylist);
//        BubbleSort_Mid(pt_arraylist);
//        BubbleSort_Mid_Opt(pt_arraylist);
//        SelectSort_Asc(pt_arraylist);    
//        SelectSort_Desc(pt_arraylist);    
//        InsertSort(pt_arraylist);
//        ShellSort(pt_arraylist);
//        QuickSort(pt_arraylist, 0, pt_arraylist->len-1);
        QuickSort_Opt(pt_arraylist, 0, pt_arraylist->len-1);
        show((char *)"排序后 ", pt_arraylist);
    } 

    
    return 0;
}

 

测试头文件

//sort.h
#define True 1 
#define False 0
#define NUMSIZE 20
typedef struct {
    int array[NUMSIZE];
    int len;
}ArrayList, *PtArrayList; 

void swap(int * first, int * second);
void show(char * info, PtArrayList * pt_arraylist); 
void Init_Data(PtArrayList pt_arraylist); 
void BubbleSort_Low(PtArrayList * pt_arraylist);
void BubbleSort_Mid(PtArrayList * pt_arraylist);
void BubbleSort_Mid_Opt(PtArrayList pt_arraylist);
void SelectSort_Asc(PtArrayList pt_arraylist);
void SelectSort_Desc(PtArrayList pt_arraylist);
void InsertSort(PtArrayList pt_arraylist);
void ShellSort(PtArrayList pt_arraylist);
int FindPos(PtArrayList pt_arraylist, int low, int high);
void QuickSort(PtArrayList pt_arraylist, int low, int high);

#include "sort_function.cpp"

 

 

 函数具体实现

//sort_function.cpp
void Init_Data(PtArrayList pt_arraylist)
{
    char s[] = "请输入不大于20的序列长度";
    printf("%s___\b\b",s);
    while(!scanf("%d", &pt_arraylist->len) || (pt_arraylist->len > NUMSIZE))
    {
        printf("%s\n",s);
        if(pt_arraylist->len > NUMSIZE)
        {
            printf("当前序列长度为%d 过长\n", pt_arraylist->len);
            continue;
        }
        scanf("%*s");
    }
    
    srand(time(0)); //随机初始化rand()函数
    for(int i=0; i<pt_arraylist->len; i++)
    {
        pt_arraylist->array[i] = rand()%200-100;
    }
    
}

void QuickSort_Opt(PtArrayList pt_arraylist, int low, int high)
{
    //快速排序--尾递归优化 
    int pos;
    while(low<high)
    {
        pos = FindPos(pt_arraylist, low, high);
        QuickSort(pt_arraylist, low, pos-1