面试题-常用的排序方法大全

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

using namespace std;

void QuickSort(int a[], int low, int high)
{
if(low >= high) {
return;
}

int begin = low;
int end = high;
int key = a[begin];

cout<<"sort ... begin="<<begin<<"  end="<<end<<"  key="<<key<<endl;

while(begin < end)
{
while(begin < end && a[end] >= key)
{
--end;
}

a[begin] = a[end];
while(begin < end && a[begin] <= key)
{
++begin;
}

a[end] = a[begin];
}

a[begin] = key;
QuickSort(a, low, begin-1);
QuickSort(a, begin+1, high);
}

void BubbleSort(int a[], int end)
{
int k = 0;
int flag = end;

while(flag > 0)
{
k = flag;
flag = 0;
for(int j=1; j<k; ++j)
{
if(a[j-1] > a[j]) {
swap(a[j], a[j-1]);
flag = j;
}
}
}
}

template<typename T>
void MinHeapify(T* array, int size, int element)
{
int lchild = element*2+1;
int rchild = lchild+1;

while(rchild < size)
{
cout<<"lchild ="<<lchild<<"  rchild = "<<rchild<<"  size = "<<size<<endl;
if(array[element] <= array[lchild] && array[element] <= array[rchild]) {
return;
}

if(array[lchild] <= array[rchild]) {
swap(array[element], array[lchild]);
element = lchild;
}
else {
swap(array[element], array[rchild]);
element = rchild;
}

lchild = element*2+1;
rchild = lchild+1;
}

if(lchild<size && array[lchild]<array[element]) {
swap(array[lchild], array[element]);
}

return;
}

template<typename T>
void HeapSort(T* array, int size)
{
int i;
for(i=size-1; i>=0; i--)
{
MinHeapify(array, size, i);
}

while(size > 0)
{
cout<<"size = "<<size<<" "<<array[size-1]<<" "<<array[0]<<endl;
swap(array[size-1], array[0]);
size--;
MinHeapify(array, size, 0);
}
}

void InsertSort(int a[], int n)
{
for(int i=1; i<n; ++i)
for(int j=i-1; j>=0 && a[j]>a[j+1]; --j)
swap(a[j], a[j+1]);
}

void SheelSort(int a[], int n)
{
for(int gap=n/2; gap>0; gap/=2)
{
for(int i=gap; i<n; ++i)
{
for(int j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap)
{
swap(a[j], a[j+gap]);
}
}
}
}

void SelectSort(int a[], int n)
{
int idx = 0;
for(int i=0; i<n; ++i)
{
idx = i;
for(int j=i; j<n; ++j)
{
if(a[j] < a[idx])
idx = j;
}

swap(a[i], a[idx]);
}
}

void mergeArray(int a[], int first, int mid, int last)
{
cout<<"merge array"<<endl;
int i=first, j=mid+1;
int k=0;
int tmp[10] = {0};

while(i<=mid && j<=last)
{
if(a[i]<=a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
}

while(i<=mid)
tmp[k++] = a[i++];

while(j<=last)
tmp[k++] = a[j++];

for(int j=0, i=first; i<=last; ++i, ++j)
a[i] = tmp[j];

for(int i=0; i<10; ++i)
{
cout<<" "<<a[i]<<" ";
}
cout<<endl;
}

void grouping(int a[], int first, int last)
{
cout<<"grouping ";

if(first < last) {
int mid = (first + last)/2;
grouping(a, first, mid);
grouping(a, mid+1, last);
mergeArray(a, first, mid, last);
}
}

void MergeSort(int a[], int n)
{
grouping(a, 0, n-1);
}

int main()
{
int a[] = {49,38,65,97,26,13,27,48,55,4};
//QuickSort(a, 0, sizeof(a)/sizeof(a[0])-1); // 快排
//BubbleSort(a, sizeof(a)/sizeof(a[0]));     // 冒泡
//HeapSort(a, sizeof(a)/sizeof(a[0]));       // 堆
//InsertSort(a, sizeof(a)/sizeof(a[0]));     // 插入
//SheelSort(a, sizeof(a)/sizeof(a[0]));      // 希尔
//SelectSort(a, sizeof(a)/sizeof(a[0]));     // 选择
MergeSort(a, sizeof(a)/sizeof(a[0]));        // 归并
for(int i=0; i<sizeof(a)/sizeof(a[0]); ++i) {
cout<<a[i]<<"  ";
}

return 1;
}