① 将序列天生堆，调解成最大堆
② 弹出堆顶，天生新序列，重复 ① 。
（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; 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, 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 < flag); do j--; while(key[j] > flag); if(i < j) swap(key, 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 > key[j]) swap(key, 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 > tmp) { arr[i + gap] = arr; 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]++; } for (int i = 0; i < n; i++){ for (int j = 0; j < hash_map; j++) printf("%d ", i); } }//产生随机序列 void Init(int key[], int n){ cout<<"\n\n随机序列："; for(int i=0; i<n; i++){ key = rand()%20; cout<<key<<" "; }} //输出有序序列 void output(int key[], int n){ for(int i=0; i<n; i++) cout<<key<<" ";}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;} |
