排序题目实验_从键盘上输入若干整数以零为结束标志建立一个无序,的顺序表采用冒泡排序对输

希尔排序

【问题描述】给出一组数据，请用希尔排序将其按照从小到大的顺序排列好。

【输入形式】原始数据，以0作为输入的结束；第二行是增量的值，都只有3个。

【输出形式】每一趟增量排序后的结果

【样例输入】

8 3 6 1 68 12 19 3 1 0

5 3 1

【样例输出】

8 3 3 1 68 12 19 6 1
1 3 1 8 6 3 19 68 12
1 1 3 3 6 8 12 19 68

【样例输入】

5 3 9 8 2 4 1 7 10 6 0

4 2 1

【样例输出】

2 3 1 7 5 4 9 8 10 6
1 3 2 4 5 6 9 7 10 8
1 2 3 4 5 6 7 8 9 10

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
void ShellInsert(vector<int>&s, int gap)
{
	for (int i = gap; i < s.size(); i++)
	{
		for (int j = i-gap; j >=0 ; j-=gap)
		{
			if (s[j] > s[j + gap])
			{
				int temp = s[j + gap];
				s[j + gap] = s[j];
				s[j] = temp;
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	vector<int>s;
	int temp;
	while (cin>>temp)
	{
		if (temp != 0)
		{
			s.push_back(temp);
		}
		else
		{
			break;
		}
	}
	int num[3];
	cin >> num[0] >> num[1] >> num[2];
	for (int i = 0; i < 3; i++)
	{
		ShellInsert(s, num[i]);
		for (int j = 0; j < s.size(); j++)
		{
			cout << s[j] << " ";
		}
		cout << endl;
	}
}
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

堆排序

【问题描述】请用堆排序的方法对一组数据进行排序，并给出建堆以及每一趟堆排序的结果。
【输入形式】一组数据，以0作为输入的结束。
【输出形式】建大根堆的结果，以及每一趟堆排序的结果。
【样例输入】

8 3 6 1 68 12 0

【样例输出】

68 8 12 1 3 6
12 8 6 1 3 68
8 3 6 1 12 68
6 3 1 8 12 68
3 1 6 8 12 68
1 3 6 8 12 68

【样例输入】

12 9 26 11 38 52 99 27 66 15 32 0

【样例输出】

99 66 52 27 38 12 26 9 11 15 32
66 38 52 27 32 12 26 9 11 15 99
52 38 26 27 32 12 15 9 11 66 99
38 32 26 27 11 12 15 9 52 66 99
32 27 26 9 11 12 15 38 52 66 99
27 15 26 9 11 12 32 38 52 66 99
26 15 12 9 11 27 32 38 52 66 99
15 11 12 9 26 27 32 38 52 66 99
12 11 9 15 26 27 32 38 52 66 99
11 9 12 15 26 27 32 38 52 66 99
9 11 12 15 26 27 32 38 52 66 99

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
void adjust(int arr[], int len, int index)//index是父亲结点的下标，该函数用来将数组修改为最大堆
{
	int left = 2 * index + 1;//左子树下标
	int right = 2 * index + 2;//右子树下标
	int maxindex = index;
	if (left < len && arr[left] > arr[maxindex])
	{
		maxindex = left;
	}
	if (right < len && arr[right] > arr[maxindex])
	{
		maxindex = right;
	}//maxindex是三个下标中对应数值最大的那个

	if (maxindex != index)//如果maxindex有改变
	{
		swap(arr[maxindex], arr[index]);
		adjust(arr, len, maxindex);
	}
}
void HeapSort(int arr[], int size)
{
	for (int i = size/2 - 1; i >=0; i--)//最后一个结点是len-1，其父亲结点就是size/2-1
	{
		adjust(arr, size, i);
	}
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	for (int i = size - 1; i >= 1; i--)
	{
		swap(arr[0], arr[i]);//交换顶端的结点和末尾的结点，然后重构最大堆
		adjust(arr, i, 0);
		for (int i = 0; i < size; i++)
		{
			cout << arr[i] << " ";
		}
		cout << endl;
	}
}
int main()
{
	int data, arr[1000];
	int len = 0;
	while (cin >> data)
	{
		if (data != 0)
		{
			arr[len] = data;
			len++;
		}
		else
		{
			break;
		}
	}
	HeapSort(arr, len);
}
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

冒泡，选择，快排

问题描述】输入一组数据，以0作为输入的结束，分别采用冒泡排序、选择排序、快速排序的方法，对其进行从小到大的排序，给出排序后的结果。

【输入形式】一组数据，以0作为输入的结束

【输出形式】三种排序后的结果

【样例输入】

9 8 4 5 7 2 10 6 0
【样例输出】

2 4 5 6 7 8 9 10

2 4 5 6 7 8 9 10

2 4 5 6 7 8 9 10

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
void QuickSort(int arr[], int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	int temp = arr[begin];
	int i = begin, j = end;
	while (i != j)
	{
		while (arr[j] >= temp && j > i)
		{
			j--;
		}
		while (arr[i] <= temp && j > i)
		{
			i++;
		}
		if (j > i)
		{
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	arr[begin] = arr[i];
	arr[i] = temp;
	QuickSort(arr, begin, i - 1);
	QuickSort(arr, i + 1, end);
}
void BubbleSort(int arr[],int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}
void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}
}
int main()
{
	int arr1[1000], data, arr2[1000], arr3[1000];
	int len = 0;
	while (cin >> data)
	{
		if (data != 0)
		{
			arr1[len] = data;
			arr2[len] = data;
			arr3[len] = data;
			len++;
		}
		else
		{
			break;
		}
	}
	QuickSort(arr1, 0, len - 1);
	for (int i = 0; i < len; i++)
	{
		cout << arr1[i] << " ";
	}
	cout << endl;
	BubbleSort(arr2, len);
	for (int i = 0; i < len; i++)
	{
		cout << arr2[i] << " ";
	}
	cout << endl;
	SelectSort(arr3, len);
	for (int i = 0; i < len; i++)
	{
		cout << arr3[i] << " ";
	}
}
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

时间监测

题目描述】随机生成10000、20000、40000、80000、160000个整形数据，监测冒泡排序、选择排序、快速排序这三种排序方法各自所需要的时间，并显示其排序时间。可以将前面做过的其他排序方法加入，进行对比。

代码：

//修改N的大小即可检测不同规模数据的运行时间

#include<iostream>
#include <time.h>
#include<assert.h>
#define N 10000
using namespace std;

clock_t start, stop;     //clock_t是clock（）函数返回的变量类型
double duration;


//冒泡排序
void sort1(int a[], int n)
{
	int i, j, temp, m = 0;
	int flag;
	for (i = 0; i < n - 1; i++)
	{
		flag = 0;
		for (j = n - 1; j > i; j--)
		{
			if (a[j - 1] > a[j])
			{
				temp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = temp;
				flag = 1;
			}
		}
		if (flag == 0)break;
	}
}

//快速排序
int partition(int arr[], int left, int right)  //找基准数 划分
{
	int i = left + 1;
	int j = right;
	int temp = arr[left];

	while (i <= j)
	{
		while (arr[i] < temp)
		{
			i++;
		}
		while (arr[j] > temp)
		{
			j--;
		}
		if (i < j)
			swap(arr[i++], arr[j--]);
		else i++;
	}
	swap(arr[j], arr[left]);
	return j;

}

void quick_sort(int arr[], int left, int right)
{
	if (left > right)
		return;
	int j = partition(arr, left, right);
	quick_sort(arr, left, j - 1);
	quick_sort(arr, j + 1, right);
}

//堆排序
void AdjustDown(int a[], size_t n, int root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int a[], size_t n)
{
	assert(a);
	int parent = (n - 2) >> 1;
	//建堆
	for (; parent >= 0; --parent)
	{
		AdjustDown(a, n, parent);
	}
	for (int i = n - 1; i >= 0; --i)
	{
		swap(a[0], a[i]);
		AdjustDown(a, i, 0);
	}
}
//选择排序
void selectSort(int a[], int len)
{

	int minindex, temp;
	for (int i = 0; i < len - 1; i++)
	{
		minindex = i;
		for (int j = i + 1; j < len; j++)
		{
			if (a[j] < a[minindex])
				minindex = j;

		}
		temp = a[i];
		a[i] = a[minindex];
		a[minindex] = temp;
	}
}

int main()
{
	int i, j, temp, m = 0;
	int a[N];
	cout << "生成" << N << "个随机数" << endl << endl;
	for (i = 0; i < N; i++)
	{
		a[i] = rand() % N;
		/*printf("%5d",a[i]);
		m++;
		if (m %10==0)printf("\n");*/
	}


	start = clock();
	sort1(a, N);
	stop = clock();
	//CLOCKS_PER_SEC是一个常数，表示机器时钟每秒所走的时钟打点数，有的IDE下叫CLK_TCK
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	cout << "冒泡排序运行时间是：" << duration << "秒" << endl << endl;

	for (i = 0; i < N; i++)
		a[i] = rand() % N;
	start = clock();
	quick_sort(a, 0, N);
	stop = clock();
	//CLOCKS_PER_SEC是一个常数，表示机器时钟每秒所走的时钟打点数，有的IDE下叫CLK_TCK
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	cout << "快速排序运行时间是：" << duration << "秒" << endl << endl;

	start = clock();
	HeapSort(a, N);
	stop = clock();
	//CLOCKS_PER_SEC是一个常数，表示机器时钟每秒所走的时钟打点数，有的IDE下叫CLK_TCK
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	cout << "堆排序运行时间是：" << duration << "秒" << endl << endl;

	for (i = 0; i < N; i++)
		a[i] = rand() % N;
	start = clock();
	selectSort(a, N);
	stop = clock();
	//CLOCKS_PER_SEC是一个常数，表示机器时钟每秒所走的时钟打点数，有的IDE下叫CLK_TCK
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	cout << "选择排序运行时间是：" << duration << "秒" << endl << endl;

	return 0;
}

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177