博客声明

1 背景

今天闲来无事，把C++常用的排序方法介绍一下吧

利用排序的方法将输入的6个数字按从小到大排序

2 排序方法

2.1 冒泡排序法

2.1.1 代码

#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 代码

#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 代码

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int cmp(const void *a , const void *b);
    int arr[100000];
    int n;
	printf("%s\n", "请输入待排序的数的个数n：");
    scanf("%d", &n);
    int tmp;
	printf("%s\n", "请输入待排序的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("%d\n" , 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函数声明如下：

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 代码

#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 实现

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。