数据结构：排序

实验目标：

提示

（1）创建排序表

（2）输出排序表元素

（3）直接插入排序

（4）冒泡排序

（5）快速排序

（6）简单选择排序

---

实验代码

#include <bits/stdc++.h>
using namespace std;

#define MAXSIZE 20
typedef int KeyType;

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef struct{
    KeyType   key;
}RedType;

typedef struct{
    RedType   *r;
    int       length;
}SqList;

//创建排序表
void Create(SqList &L)
{
    cout<<"请输入排序表的长度:";
    int len;
    cin>>len;
    cout<<endl;

    L.r=(RedType *)malloc((len+1)*sizeof(RedType));
    for(int i=1;i<=len;i++)
        cin>>L.r[i].key;
    L.length=len;
}

//输出排序表元素
void Traverse(SqList L)
{
    for(int i=1;i<=L.length;i++){
        cout<<L.r[i].key<<" ";
    }
    cout<<endl;
}

void swap(SqList &L,int a,int b)//进行交换
{
    int temp=L.r[a].key;
    L.r[a].key=L.r[b].key;
    L.r[b].key=temp;
}

//直接插入排序
void InsertSort(SqList &L)
{
    int i=2,j=2;

    for(i=2;i<=L.length;++i){
        if(LT(L.r[i].key,L.r[i-1].key)){
            L.r[0]=L.r[i];
            L.r[i]=L.r[i-1];
            
            for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)
                L.r[j+1]=L.r[j];
            L.r[j+1]=L.r[0];
        }
    }
}

//冒泡排序
void BubbleSort(SqList &L)
{
    for(int end=L.length;end>0;end--){
        for(int i=0;i<end;i++){
            int temp=0;
            if(L.r[i].key>L.r[i+1].key){
                swap(L,L.r[i].key,L.r[i+1].key);
            }
        }
    }
} 

//快速排序
void QuickSort(SqList &L,int begin,int end)
{
    if (begin >= end) return;

	int left = begin,right = end;
	int key1 = L.r[begin].key;

	while (begin < end)
	{
		while (L.r[end].key>=key1 && begin < end) --end;
		L.r[begin].key = L.r[end].key;
		while (L.r[begin].key<=key1 && begin < end) ++begin;
		L.r[end].key = L.r[begin].key;
	}
	L.r[begin].key=key1;

	int key2=begin;
	QuickSort(L,left,key2 - 1);
	QuickSort(L,key2+1,right);
}

int SelectMinKey(SqList &L,int i){
    int pos=i;
    int ans=L.r[i].key;
    for(int j=i+1;j<=L.length;j++){
        if(L.r[j].key<ans){
            pos=j;
            ans=L.r[pos].key;
        }
    }
    return pos;
}

//简单选择排序
void SelectSort(SqList &L) 
{
    for(int i=1;i<=L.length;i++){
        int j=SelectMinKey(L,i);//找出i到length中key最小的位置
        if(i!=j){
            swap(L,i,j);
        }
    }
}

int main()
{
    SqList L; 
    int c = 0;
    while (c != 5) {
        cout << endl << "1. 直接插入排序";
        cout << endl << "2. 冒泡排序";
        cout << endl << "3. 快速排序";
        cout << endl << "4. 简单选择排序";
        cout << endl << "5. 退出";
        cout << endl << "选择功能(1~5):";
        cin >> c;
          
        switch (c)
        {
        case 1:{
            Create(L); 
            cout<<"排序前数据:"; 
            Traverse(L);
            InsertSort (L);
            cout<<"排序后数据:"; 
            Traverse(L);
            break;
        }

        case 2:{
            Create(L);
            cout<<"排序前数据:"; 
            Traverse(L);
            BubbleSort(L);
            cout<<"排序后数据:"; 
            Traverse(L);
            break;
        }

        case 3:{
             Create(L); 
            cout<<"排序前数据:"; 
            Traverse(L);
            int begin=1;
            int end=L.length;
            QuickSort(L,begin,end);
            cout<<"排序后数据:"; 
            Traverse(L);
            break;
        }

        case 4:{
            Create(L); 
            cout<<"排序前数据:"; 
            Traverse(L);
            SelectSort(L);
            cout<<"排序后数据:"; 
            Traverse(L);
            break;
        }

        case 5:cout<<"结束操作"<<endl; break;
        }
    } 

    system("pause");
    return 0;
}