今天闲来无事，把C++常用的排序方法介绍一下吧
利用排序的方法将输入的6个数字按从小到大排序
2 排序方法
2.1 冒泡排序法
2.1.1 代码
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
|
#include <iostream>
using namespace std;
#define N 6 //宏定义需要进行排序的数字个数
int main()
{
int temp;
int list[N] = { 0 }; //定义数组用于存放无序的数列，数组里的元素初始化为0
cout << "请输入6个无序的数据：" << endl;
for (temp = 0; temp < N; temp++)
cin >> list[temp]; //依次从键盘上输入N个无序数据存放在数组list中
cout <<"排序前的序列："<< endl; //先将排序前的数据输出，以便对比排序后的情况
for (temp = 0; temp < N; temp++)
cout << list[temp] << " ";
cout << endl;
void sort(int a[]); //函数声明
sort(list); //函数调用
cout << "排序后的序列：" << endl;
for (temp = 0; temp < N; temp++)
cout << list[temp] << " ";
cout << endl;
return 0;
}
void sort(int a[])
{
int i, j, t;
for(j = 0; j < 6; j++)
for(i = 0; i < j - i; i++)
if (a[i] > a[i + 1])
{
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t; //如果前面数据大于后面数据，则进行交换
}
}
|
2.1.2 实现
2.2 选择排序法
2.2.1 代码
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
|
#include <iostream>
using namespace std;
#define N 6 //宏定义需要进行排序的数字个数
int main()
{
int temp;
int list[N] = { 0 }; //定义数组用于存放无需的数列，数组里的元素初始化为0
cout << "请输入N个无序的数据：" << endl;
for (temp = 0; temp < N; temp++)
cin >> list[temp]; //依次从键盘上输入N个无序数据存放在数组list中
cout << "排序前的序列：" << endl; //先将排序前的数据输出，以便对比排序后的情况
for (temp = 0; temp < N; temp++)
cout << list[temp] << " ";
cout << endl;
void select_sort(int array[], int n); //函数声明
select_sort(list, N); //函数调用
cout << "排序后的序列：" << endl;
for (temp = 0; temp < N; temp++)
cout << list[temp] << " ";
cout << endl;
return 0;
}
void select_sort(int array[], int n)
{
int i, j, k, t;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
if (array[j] < array[k])
k = j;
t = array[k];
array[k] = array[i];
array[i] = t; //如果前面数据大于后面数据，则进行交换下标
}
}
|
2.2.2 实现
2.3 快速排序
2.3.1 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>
#include <stdlib.h>
int main()
{
int cmp(const void *a , const void *b);
int arr[100000];
int n;
printf("%sn", "请输入待排序的数的个数n：");
scanf("%d", &n);
int tmp;
printf("%sn", "请输入待排序的n个数：");
for(tmp = 0; tmp < n; tmp++)
scanf("%d" , &arr[tmp]);
qsort(arr , n , sizeof(arr[0]) , cmp);
for(tmp = 0; tmp < n - 1; tmp++)
printf("%d " , arr[tmp]);
printf("%dn" , arr[tmp]);
return 0;
}
int cmp(const void *a , const void *b)
{
return *(int *)a - *(int *)b;
}
|
2.3.2 实现
2.3.3 知识延伸
qsort函数包含在#include< stdlib.h>中
qsort函数声明如下：
1
|
void qsort(void * base,size_t nmemb,size_t size ,int(*compar)(const void *,const void *));
|
参数说明：
- base,要排序的数组
- nmemb,数组中元素的数目
- size,每个数组元素占用的内存空间，可使用sizeof函数获得
2.4 折半插入排序
2.4.1 代码
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
|
#include <iostream>
using namespace std;
int arr[1000], n;
int main() {
void BInsertSort();
int i;
cout << "请输入待排序的数的个数n：" << endl;
while(cin >> n) {
cout << "请输入待排序的n个数：" << endl;
for(i = 0; i < n; i++)
cin >> arr[i];
BInsertSort();
for(i = 0; i < n; i++)
cout<< arr[i] <<" ";
cout << endl;
}
return 0;
}
void BInsertSort() {
int i;
for(i = 1; i < n; i++) {
int low = 0 , high = i - 1 , mid;
while(low <= high) {
mid = (low + high) / 2;
if(arr[mid] >= arr[i])
high = mid - 1;
else
low = mid + 1;
}
int temp = arr[i];
int j;
for(j = i; j > low; j--)
arr[j] = arr[j - 1];
arr[low] = temp;
}
}
|
2.4.2 实现
转载请注明来源，欢迎对文章中的引用来源进行考证，指出任何有错误或不够清晰的表达，可以邮件至 [email protected]
近期评论