iOS 算法七大排序算法~ demo

//联系人:石虎QQ: 1224614774昵称:嗡嘛呢叭咪哄

注意:详细算法请看 http://blog.csdn.net/shihuboke/article/details/77217717

#include<assert.h>

#include<stdlib.h>

#include<iostream>

#include<assert.h>

#include<stdlib.h>

usingnamespacestd;

#define RADIX_1010

#define KEYNUM_3110

voidSwap(int* a,int* b)

{

inttemp;

temp = *a;

*a = *b;

*b = temp;

}

#pragma mark - 1.插入排序

voidInsertSort(int* a,intn)

{

for(inti =0; i

{

inttmp;

intend = i;

tmp = a[end +1];

while(end>=0)

{

if(a[end]>tmp)

{

a[end +1] = a[end];

--end;

}

else{

break;

}

}

a[end +1] = tmp;

}}

#pragma mark - 2.希尔排序

voidShellSort(int* a,intn)

{

intgap = n;

while(gap>1)

{

gap=gap/3+1;

for(inti =0; i < n-gap;i++)

{

inttmp;

intend = i;

tmp = a[end + gap];

while(end>=0){

if(a[end]>tmp){

a[end + gap] = a[end];

--end;

}

else{

break;

}

}

a[end + gap] = tmp;

}

#pragma mark - 3.选择排序

voidSelectSort1(int* a,intn)

{

intmin,i ;

for(i =0; i < n;i++)

{

min = i;

for(intj = i +1; j < n;j++)

{

if(a[j]<=a[min])

{

min = j;

}

}

swap(a[min], a[i]);

}

voidSeleteSort2(int* a,intn)

{

intmax, min, i, j;

for(i =1; i <=n /2;i++)

{

min = i; max = i;

for(j = i +1; j <=n-i;j++)

{

if(a[j] >a[max])

{

max = j;

}

if(a[j]

{

min = j;

}

swap(a[i], a[min]);

swap(a[n-i], a[max]);

}

#pragma mark - 4.堆排序

voidAdjustHeap(int*a,introot,intlen)

{

intparent = root;

intchild =2* parent +1;

while(child

{

if(child+1

{

++child;

}

if(a[parent]

{

swap(a[parent],a[child]);

parent= child;

child =2* parent +1;

}

else

{

break;

}

voidBuildHeap(int* a,intlen)

{

for(inti = (len -1) /2; i >=0; i--)

{

AdjustHeap(a, i, len);

}

voidHeapSort(int* a,intlen)

{

BulidHeap(a, len);

for(inti = len -1; i >0;i--)

{

inttemp = a[i]; a[i] = a[0]; a[0] = temp;

AdjustHeap(a,0, i);

}

#pragma mark - 5.冒泡排序

voidBubbleSort(int* a,intlen)

{

for(inti=0; i < len;i++)

{

for(intj =0; j < len - i-1;j++)

{

if(a[j]>a[j+1])

{

swap(a[j],a[j+1]);

}

}

#pragma mark - 6.快速排序

intGetMidIndex(int* a,intleft,intright)

{

intmid = left+(left - right) /2;

if(a[left]

{

if(a[mid]

{

returnmid;

}

elseif(a[left]>a[right])

{

returnleft;

}

else

returnright;

}

else//left>mid

{

if(a[mid]>a[right])

{

returnmid;

}

elseif(a[left] < a[right])

{

returnleft;

}

else

returnright;

}

intPartSort1(int* a,intleft,intright)

{

intmid =GetMidIndex(a, left,right);

swap(a[mid],a[right]);

intkey = a[right];

intbegin = left;

intend = right;

while(begin < end)

{

while(begin

{

++begin;

}

while(begin=key)

{

--end;

}

if(begin < end)

swap(a[begin], a[end]);

}

swap(a[begin],a[right]);

returnbegin;

}

voidQuickSort(int* a,intleft,intright)

{

assert(a);

if(left >= right)

return;

if(right - left <5)

{

InsertSort(a + left, right - left +1);

}

else

{

intdiv =PartSort1(a, left, right);

QuickSort(a, left, div -1);

QuickSort(a, div +1, right);

}

#pragma mark - 7.归并排序

voidMerge(int* a,int* tmp,intbegin1,intend1,intbegin2,intend2)

{

intpos = begin1;

intindex = begin1;

while(begin1<=end1&&begin2<=end2)

{

if(a[begin1]

{

tmp[index++] = a[begin1++];

}

else

{

tmp[index++] = a[begin2++];

}

while(begin1<=end1)

{

tmp[index++] = a[begin1++];

}

while(begin2<=end2)

{

tmp[index++] = a[begin2++];

}

memcpy(a+pos,tmp+pos,sizeof(int)*(end2-pos+1));

}

void_MergeSort(int* a,int* tmp,intleft,intright)

{

if(left>=right)

{

return;

}

intmid = left + (right-left) /2;

_MergeSort(a,tmp,left,mid);

_MergeSort(a, tmp, mid +1, right);

Merge(a, tmp, left, mid, mid +1, right);

}

voidMergeSort(int* a,intlen)

{

assert(a);

int* tmp =newint[len];

_MergeSort(a,tmp,0,len-1);

delete[] tmp;

}

voidDisplay(int* a,intn)

{

for(inti =0; i < n;i++)

{

cout << a[i] <<" ";

}

cout << endl;

}

voidTestInsertSort()

{

inta[] = {2,1,3,4,7,4,6,8,9,10};