- 堆排序（实现难易：⭐⭐⭐）
① 将序列生成堆，调整成最大堆
② 弹出堆顶，生成新序列，重复 ① 。
- 快速排序（实现难易：⭐⭐⭐）
（a）先移动 j 找到 <= low 的数，再移动 i 找到>= low 的数：
① 若 i < j ，两者交换，继续移动。 ② 若 i >= j，j 与 low 交换。
（b）交换后数列划分，分别令各子数列第一个数为 low，重复（a）。
- 归并排序（实现难易：⭐⭐⭐）
- 希尔排序（实现难易：⭐⭐）
- 直接插入排序（实现难易：⭐）
将下标 1~n-1 的数依次插入准序数列。
- 简单选择排序（实现难易：⭐）
将下标 j=i+1~n-1 的最小数依次放在 i=0~n-2。
- 冒泡排序（实现难易：⭐）
将下标 i=n-1~1 的数从后往前两两相邻数 j=i-1~0 比较，若反序则交换。
- 哈希排序（实现难易：⭐）
运用一个数组来记录每个数出次数，也就是将序列和数组的下标进行对应，从而实现排序。
#include <iostream>
#include <stdlib.h>
using namespace std;
//1、直接插入排序
void InsertSort(int key[], int n){
int i,j;
for(i=1; i<n; i++){ //遍历第 2~n-1 个元素
int insert = key[i];
for(j=i-1; j>=0; j--){
if(insert < key[j])
key[j+1] = key[j];
else break;
}
key[j+1] = insert;
}
}
//2、简单选择排序
void SelectSort(int key[], int n){
int small,i,j;
for(i=0; i<n-1; i++){ //遍历第 1~n-1 个元素
small = i;
for(j=i+1; j<n; j++){ //遍历第 i+1~n 个元素
if(key[j] < key[small])
small = j;
}
if(small != i)
swap(key[i], key[small]);
}
}
//3、冒泡排序
void BubbleSort(int key[], int n){
int i,j;
for(i=n-1; i>0; i--){ //遍历第 2~n 个元素
bool isSwap = false;
for(j=0; j<i; j++){ //遍历第 1~i 个元素
if(key[j] > key[j+1]){
swap(key[j],key[j+1]);
isSwap = true;
}
}
if(!isSwap) break;
}
}
//4、快速排序
int Partition(int key[], int low,int high){
int i = low,j = high + 1;
int flag = key[low]; //当前分割元素
do{
do i++;
while(key[i] < flag);
do j--;
while(key[j] > flag);
if(i < j)
swap(key[i], key[j]);
}while(i < j);
swap(key[low], key[j]);
return j; //下一个分割元素
}
void QuickSort(int key[], int low, int high){
int k;
if(low < high){
k = Partition(key,low,high);
QuickSort(key,low,k-1);
QuickSort(key,k+1,high);
}
}
void QuickSort(int key[], int n){
QuickSort(key,0,n-1);
}
//5、归并排序
void _merge(int key[], int low, int mid, int high) { //合并
for (int i = 0; i < mid; i++) {
for (int j = mid; j < high; j++) {
if (key[i] > key[j])
swap(key[i], key[j]);
}
}
}
void MergeSort(int key[], int low, int high) {
if (low < high) {
int length = high - low;
if (length == 1) {
if (key[low] > key[high])
swap(key[low],key[high]);
}
for (int i=length/2; i>0; i=i/2) { //分治
MergeSort(key, low, low + i);
MergeSort(key, high - i, high);
_merge(key, low, i, high); //i为有序序列长度
}
}
}
//6、堆排序
void AdjustDown(int heap[], int current, int border){
int tmp = heap[current];
while (2*current+1<=border){
int child = 2*current+1; //左孩子
if (child+1<=border && heap[child]<heap[child+1])
child++;
if (heap[child] > heap[current]) {
heap[current] = heap[child];
heap[child] = tmp;
}
else break;
current=child;
}
}
void HeapSort(int heap[],int n){
for(int i=(n-2)/2; i>=0; i--) //初始调整
AdjustDown(heap,i,n-1);
for(int j=n-1; j>0; j--){
swap(heap[0],heap[j]); //交换
AdjustDown(heap, 0, j-1); //调整
}
}
//7、希尔排序
void shell(int arr[], int n, int start, int gap) {
for (int j = start + gap; j < n; j += gap) {
int i = j - gap;
int tmp = arr[j];
while (i >= start && arr[i] > tmp) {
arr[i + gap] = arr[i];
i -= gap;
}
arr[i + gap] = tmp;
}
}
void ShellSort(int arr[], int n) {
if (n <= 1)
return;
for (int gap=n/2; gap>=1; gap/=2) {
for (int i=0; i<gap; i++)
shell(arr, n, i, gap);
}
}
//8、哈希排序
void HashSort(int key[], int n){
int hash_map[n] = {0};
for (int i = 0; i < n; i++){
hash_map[key[i]]++;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < hash_map[i]; j++)
printf("%d ", i);
}
}
//产生随机序列
void Init(int key[], int n){
cout<<"\n\n随机序列：";
for(int i=0; i<n; i++){
key[i] = rand()%20;
cout<<key[i]<<" ";
}
}
//输出有序序列
void output(int key[], int n){
for(int i=0; i<n; i++)
cout<<key[i]<<" ";
}
int main(){
int key[500000], n;
cout<<"\n随机序列长度："; cin>>n;
Init(key,n); InsertSort(key,n);
cout<<"\n\n直接插入排序："; output(key,n);
Init(key,n); SelectSort(key,n);
cout<<"\n\n简单选择排序："; output(key,n);
Init(key,n); BubbleSort(key,n);
cout<<"\n\n冒泡排序："; output(key,n);
Init(key,n); QuickSort(key,n);
cout<<"\n\n快速排序："; output(key,n);
Init(key,n); MergeSort(key,0,n-1);
cout<<"\n\n归并排序："; output(key,n);
Init(key,n); HeapSort(key,n);
cout<<"\n\n堆排序："; output(key,n);
Init(key,n); ShellSort(key,n);
cout<<"\n\n希尔排序："; output(key,n);
Init(key,n);
cout<<"\n\n哈希排序："; HashSort(key,n);
cout<<"\n\n";
return 0;
}
