#include<iostream>
using namespace std;
void swap(int * t, int i, int j){
int temp = t[i];
t[i] = t[j];
t[j] = temp;
}
//归并排序：
void Merge(int*a, int*temp,int low, int mid, int high){
int i, lEnd, NumElements, tempos;
lEnd = mid - 1;
tempos = low;
NumElements = high - low + 1;
while (low < lEnd && mid <= high){
if (a[low] <= a[mid]){
temp[tempos++] = a[low++];
}
else{
temp[tempos++] = a[mid++];
}
}
while (low <= lEnd){
temp[tempos++] = a[low++];
}
while (mid <= high){
temp[tempos++] = a[mid++];
}
for (i = 0; i < NumElements; i++, high--){
a[high] = temp[high];
}
}
void msort(int *a, int *temp, int low, int high){
if (low >= high)return;
int middle = (low + high) / 2;
msort(a, temp, low, middle);// 对[low,mid]递归做归并排序
msort(a, temp, middle + 1, high);//对[mid+1,high]递归做归并排序
Merge(a, temp, low, middle + 1, high);//组合，把两个有序区合并为一个有序区
}
void merge_sort(int*a, int len){
int *temp = NULL;
temp = new int[len];
if (temp != NULL){
msort(a, temp, 0, len - 1);
delete []temp;
}
}
// 堆排序：
int heapsize = 0;
//返回左节点的索引
int Left(int index){ return ((index << 1) + 1);
}
int Right(int index){
return ((index << 1) + 2);
}
void maxHeapify(int *a, int index){
int largest = 0;
int left = Left(index);
int right = Right(index);
if ((left <= heapsize) && (a[left] > a[index]))
largest = left;
else
largest = index;
if ((right <= heapsize) && (a[right] > a[largest]))
largest = right;
if (largest != index){
swap(a, index, largest);
maxHeapify(a, largest);
}
}
void buildMaxheap(int array[], int length){
int i;
heapsize = length;
for (i = length >> 1; i >= 0; i--)
{
maxHeapify(array, i);
}
}
void heap_sort(int *a, int leng){
buildMaxheap(a, leng-1);//建立大堆
for (int i = (leng - 1); i >= 1; i--){
swap(a, i, 0);
heapsize--;
maxHeapify(a, 0);
}
}
// 选择排序：
void choice(int *a, int len){
int i, j, x, l;
for (int i = 0; i < len - 1; i++){
x = a[i];
l = i;
for (j = i; j < len; j++){
if (a[j] < x){
x = a[j];
l = j;
}
}
a[l] = a[i];
a[i] = x;
}
}
//冒泡排序：
void maopao(int *a, int len){
int flag = 0;
for (int i = 0; i <len-1; i++){
for (int j = len-1; j > i; j--){
if (a[j] < a[j - 1])
swap(a, j, j - 1);
flag = 1;
}
if (flag != 1){
break;
}
}
}
//快速排序：
int fastpaixu(int a[], int low, int high){
int pivot = a[low];
while (low < high){
while (low < high&& a[high] >= pivot){
high = high - 1;
}
swap(a, low, high);
while (low < high&& a[low] < pivot){
low = low + 1;
}
swap(a, low, high);
}
return low;
}
void fast(int a[], int low, int high){
int pirot;
if (low < high){
pirot = fastpaixu(a, low, high);
fast(a, low, pirot - 1);
fast(a, low+1, high);
}
}
//希尔排序：
void shell_sort(int *a, int len){
int h, i,j, temp;
for (h = len / 2; h > 0; h=h/2){
for (i = h; i < len; i++){
temp = a[i];
for (j = i - h; (j >= 0 && temp < a[j]); j -= h){
a[j + h] = a[j];
}
a[j + h] = temp;
}
}
}
int main(void){
int data[9] = { 54, 38, 96, 23, 15, 72, 60, 45, 83 };
//fast(data, 0, 8); //快速排序
//maopao(data, 9);//冒泡排序
//choice(data, 9);//选择排序
//heap_sort(data, 9);//堆排序
//merge_sort(data, 9);
shell_sort(data, 9);
for (int i = 0; i < 8; i++)
{
cout << data[i] <<" ";
}
return 0;
}
