- 堆排序（實(shí)現(xiàn)難易：???）
① 將序列生成堆悠垛，調(diào)整成最大堆
② 彈出堆頂油航，生成新序列啥箭，重復(fù) ① 。
- 快速排序（實(shí)現(xiàn)難易：???）
（a）先移動 j 找到 <= low 的數(shù)爹梁，再移動 i 找到>= low 的數(shù)：
① 若 i < j 右犹，兩者交換，繼續(xù)移動姚垃。 ② 若 i >= j念链，j 與 low 交換。
（b）交換后數(shù)列劃分积糯，分別令各子數(shù)列第一個(gè)數(shù)為 low掂墓，重復(fù)（a）。
- 歸并排序（實(shí)現(xiàn)難易：???）
- 希爾排序（實(shí)現(xiàn)難易：??）
- 直接插入排序（實(shí)現(xiàn)難易：?）
將下標(biāo) 1~n-1 的數(shù)依次插入準(zhǔn)序數(shù)列絮宁。
- 簡單選擇排序（實(shí)現(xiàn)難易：?）
將下標(biāo) j=i+1~n-1 的最小數(shù)依次放在 i=0~n-2梆暮。
- 冒泡排序（實(shí)現(xiàn)難易：?）
將下標(biāo) i=n-1~1 的數(shù)從后往前兩兩相鄰數(shù) j=i-1~0 比較，若反序則交換绍昂。
- 哈希排序（實(shí)現(xiàn)難易：?）
運(yùn)用一個(gè)數(shù)組來記錄每個(gè)數(shù)出次數(shù)啦粹，也就是將序列和數(shù)組的下標(biāo)進(jìn)行對應(yīng)偿荷，從而實(shí)現(xiàn)排序。
#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 個(gè)元素
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 個(gè)元素
small = i;
for(j=i+1; j<n; j++){ //遍歷第 i+1~n 個(gè)元素
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 個(gè)元素
bool isSwap = false;
for(j=0; j<i; j++){ //遍歷第 1~i 個(gè)元素
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]; //當(dāng)前分割元素
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; //下一個(gè)分割元素
}
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--) //初始調(diào)整
AdjustDown(heap,i,n-1);
for(int j=n-1; j>0; j--){
swap(heap[0],heap[j]); //交換
AdjustDown(heap, 0, j-1); //調(diào)整
}
}
//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);
}
}
//產(chǎn)生隨機(jī)序列
void Init(int key[], int n){
cout<<"\n\n隨機(jī)序列：";
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隨機(jī)序列長度："; 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;
}
