使用了三种常用的排序方法:冒泡排序,选择排序和快速排序

1.冒泡排序法(时间复杂度O(n2))

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

maopao_sort

2.选择排序法(时间复杂度为O(nlog2n))

算法描述:选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换。

xuanze_sort

3.快速排序法

quick_sort
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
另外,汉字与字母不同,每个汉字需要两个字节来存放,所以需要两个char类型变量;此题还可以使用结构体来实现。

C语言实例:

输入输出结果:

sort_result

代码实现:

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
iostream>
#include<string.h>
using namespace std;

//1.冒泡排序法。
void sort1(char* x, int size)
{
int count[50] = {};//计数数组count
char index[50][2] = {};//临时数组index
int i, j, k = 0, ti;
char tc1,tc2;//交换时的中间变量,其中汉字需要两字节存放
for (i = 0; i < size; i+=2)
{
for (j = i - 2; j >= 0; j-=2)
{
if (x[i] == x[j]&&x[i+1]==x[j+1])
break;
}
if (j == -2)
{
index[k][0] = x[i];//统计有多少不重复的字符
index[k][1] = x[i + 1];
k++;
}
}
for (i = 0; i < k; i++)
{
for (j = 0; j < size; j+=2)
{
if (index[i][0] == x[j]&&index[i][1]==x[j+1])
count[i]++;//记录每个字符出现次数
}
}
for (i = 1; i < k; i++)//记趟数
{
for (j = 0; j < k - i; j++)
{
if (count[j] > count[j + 1])
{
ti = count[j], count[j] = count[j + 1], count[j + 1] = ti;
tc1 = index[j][0], index[j][0] = index[j + 1][0], index[j + 1][0] = tc1;
tc2 = index[j][1], index[j][1] = index[j + 1][1], index[j + 1][1] = tc2;
}
}
}
for (i = 0; i < k; i++)
printf("%c%c:%d ", index[i][0],index[i][1], count[i]);
}


//2.选择排序法。
void sort2(char* x, int size)
{
int count[50] = {};//计数数组count
char index[50][2] = {};//临时数组index
int i, j, k = 0, ti;
char tc1, tc2;//交换时的中间变量tc1.tc2,其中汉字需要两字节存放
for (i = 0; i < size; i += 2)
{
for (j = i - 2; j >= 0; j -= 2)
{
if (x[i] == x[j] && x[i + 1] == x[j + 1])
break;
}
if (j == -2)
{
index[k][0] = x[i];//统计有多少不重复的字符
index[k][1] = x[i + 1];
k++;
}
}
for (i = 0; i < k; i++)
{
for (j = 0; j < size; j += 2)
{
if (index[i][0] == x[j] && index[i][1] == x[j + 1])
count[i]++;//记录每个字符出现次数
}
}
for (i = 1; i < k; i++)//记趟数
{
int max = 0;//首先查找最大值并存放在max中
for (j = 1; j < k - i; j++)
if (count[max] < count[j])
max = j;
ti = count[max], count[max] = count[k - i], count[k - i] = ti;
tc1 = index[max][0], index[max][0] = index[k - i][0], index[k - i][0] = tc1;
tc2 = index[max][1], index[max][1] = index[k - i][1], index[k - i][1] = tc2;
}
for (i = 0; i < k; i++)
printf("%c%c:%d ", index[i][0], index[i][1], count[i]);
}




//3.1快速排序法递归部分
void sort(char index[][2], int count[], int low, int high)
{
int i = low, j = high+1;
int key = count[low];
if (high <= low)
return;
while (true)
{
while (count[++i] < key)//从左往右找比key小的值
{
if (i == high)
break;
}
while (count[--j] > key)//从右往左找比key大的值
{
if (j == low)
break;
}
if (i >= j)
break;
char tc1, tc2;//交换时的中间变量tc1.tc2
int ti;//int型变量中间值
ti = count[j], count[j] = count[i], count[i] = ti;
tc1 = index[j][0], index[j][0] = index[i][0], index[i][0] = tc1;
tc2 = index[j][1], index[j][1] = index[i][1], index[i][1] = tc2;
}
//中间值交换
int temp, tempc1, tempc2;
temp = count[low], count[low] = count[j], count[j]=temp;
tempc1 = index[low][0], index[low][0] = index[j][0], index[j][0] = tempc1;
tempc2 = index[low][1], index[low][1] = index[j][1], index[j][1] = tempc2;
sort(index, count, low, j - 1);
sort(index, count, j + 1, high);
}

//3.快速排序法
void sort3(char* x, int size)
{
int count[50] = {};//计数数组count
char index[50][2] = {};//临时数组index
int i, j, k = 0;//中间变量ti,计数变量i,j,k
for(i = 0;i < size;i += 2)
{
for (j = i - 2; j >= 0; j -= 2)
{
if (x[i] == x[j] && x[i + 1] == x[j + 1])
break;
}
if (j == -2)
{
index[k][0] = x[i];//统计有多少不重复的字符
index[k][1] = x[i + 1];
k++;
}
}
for (i = 0; i < k; i++)
{
for (j = 0; j < size; j += 2)
{
if (index[i][0] == x[j] && index[i][1] == x[j + 1])
count[i]++;//记录每个字符出现次数
}
}
sort(index, count, 0, k-1);
for (i = 0; i < k; i++)
printf("%c%c:%d ", index[i][0], index[i][1], count[i]);
}

int main()
{
char s[100];
gets_s(s);
sort1(s, strlen(s));
cout << endl;
sort2(s, strlen(s));
cout << endl;
sort3(s, strlen(s));
cout << endl;
}

该题目还可以通过结构体来实现,由于时间原因就不实际操作了。

参考资料:
百度百科快速排序法

百度百科冒泡排序法

百度百科选择排序