顺序表的各种排序_顺序表上实现排序的各种方法

#include<iostream>
using namespace std;
#define MAXSIZE 100

typedef int ElemType;
typedef struct{
	ElemType *elem;
	int length;
}SqList;
//初始化
bool InitList(SqList &L)
{
	L.elem = new ElemType[MAXSIZE];
	if(!L.elem) return false;
	L.length = 0;
	return true;
 } 
 //键盘键入值创建顺序表
void InsertData(SqList &L,int n)
{
	//n为要插入值的个数
	cout<<"请以此输入你要插入的值:"<<endl; 
	for(int i = 1;i<n+1;i++)
	{
		cin>>L.elem[i];
		L.length++;	
	}
	
} 
//show顺序表的内容
void ShowData(SqList L)
{
	for(int i = 1;i<L.length+1;i++)
		cout<<L.elem[i]<<" ";
	cout<<endl;
} 
//直接插入排序
void InsertSort(SqList L) 
{
	int j;
	for(int i=2;i<=L.length;++i)
	{
		if(L.elem[i]<L.elem[i-1])
		{
			L.elem[0] = L.elem[i];
			L.elem[i] = L.elem[i-1];
			for(j = i-2;L.elem[0]<L.elem[j];--j)
				L.elem[j+1] = L.elem[j];
			L.elem[j+1] = L.elem[0];
		}
	}
	cout<<"直接插入排序后的顺序表的内容是:"<<endl;
	ShowData(L); 
}
//折半插入排序
void BInsertSort(SqList L)
{
	int i,j,m,low,high;
	for(i=2;i<=L.length;++i)
	{
		L.elem[0] = L.elem[i];
		low = 1;
		high = i-1;
		while(low<=high)
		{
			m = (low+high)/2;
			if(L.elem[0]<L.elem[m]) high = m-1;
			else low = m+1;
		}
		for(j = i-1;j>=high+1;--j)
			L.elem[j+1] = L.elem[j];
		L.elem[high+1] = L.elem[0];
	}
	cout<<"折半插入排序后的顺序表的内容是:"<<endl;
	ShowData(L); 
 } 
 //冒泡排序
 void BubbleSort(SqList L)
 {
 	for (int i = 0; i < L.length ; i++) {
        for (int j = 1; j < L.length - i ; j++) 
		{   
            if (L.elem[j] >L.elem[j + 1]) {
                int temp = L.elem[j];
                L.elem[j] = L.elem[j + 1];
                L.elem[j + 1] = temp;
                }
            }
        }
	cout<<"冒泡排序后的顺序表的内容是:"<<endl;
	ShowData(L); 
  } 
//快速排序
int Partition(SqList &L,int low,int high)
{
	L.elem[0] = L.elem[low];
	int pivotkey = L.elem[low];
	while(low<high)
	{
		while(low<high&&L.elem[high]>=pivotkey) --high;
		L.elem[low] = L.elem[high];
		while(low<high&&L.elem[low]<=pivotkey) ++low;
		L.elem[high] = L.elem[low];
	}
	L.elem[low] = L.elem[0];
	return low;
}
void QSort(SqList &L,int low,int high)
{
	if(low<high)
	{
		int pivotloc = Partition(L,low,high);
		QSort(L,low,pivotloc-1);
		QSort(L,pivotloc+1,high);
	}
}  
void QuickSort(SqList &L)
{
	QSort(L,1,L.length);
 } 
int main()
{
	SqList L;
	InitList(L);
	int inn;
	cout<<"请输入你要插入值的个数:\n";
	cin>>inn;
	InsertData(L,inn);
	cout<<"顺序表的内容是:\n";
	ShowData(L); 
	//直接插入排序
	//InsertSort(L); 
	//折半插入排序
	//BInsertSort(L); 
	//冒泡排序
	//BubbleSort(L); 
	//快速排序
	QuickSort(L);
	ShowData(L); 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140