【算法】十大排序算法

0x55AA · 发表于 2015-1-15 20:27:01

欢迎访问技术宅的结界，请注册或者登录吧。

您需要登录才可以下载或查看，没有账号？立即注册→加入我们

×

自己根据算法思想，自己编程实现十大排序算法，当然其中也有借鉴别人的地方，所有的程序都是自己经过检验测试没有问题才放出来的。
一算法介绍
1 选择排序
选择排序的思想就是：从当前数中选出一个最大或者最小的值排在最前面，然后从剩下的数中选出剩下数的最值排在已经排序的数的后面，算法时间复杂度O(n2)，在实际工作中这种排序算法不可取。
2 冒泡排序
冒泡排序的思想就是：比如说要升序排列，那么就依次相邻两个数比较大小，然后把大的数放在后面，依次类推。冒泡排序时间复杂度O(n2)，在实际工作中这种排序算法不可取。
3 插入排序
插入排序思想就是：依次遍历数组，假设前面已经有一部分排过序的，当前待排数字跟前面的数字依次比较大小，将其插在对应顺序位置，算法时间复杂度O(n2)，在实际工作中这种排序算法不可取。
4 希尔排序
希尔排序的思想就是：希尔排序是对插入排序的改进，可以把当前数据分组，每个分组都有一定间隔，比如说原来数组的小标范围是0,1,2,3,4,5,6,7,8,9.我们把它们分成两组，0-4一组，5-9一组，这样的话，间隔就是5，我们令0,5,；1,6；2,7；3,8；4,9,它们两两比较大小。然后再减小间隔范围，或者说增多分组个数，比如此时，间隔为2，那么比较下标为0,2,4,6,8的大小，然后比较下标为1,3,5,7,9的大小。到最后间隔变为1，就变成了完全的插入排序了。
希尔排序的算法时间复杂度O(n2)。
5 快速排序
快速排序利用分治的思想，在数组中设置一个游标，从数组的两端来遍历数组，将元素和游标相比，意图达到两组数据一边游标小，一边比游标大。那么此时的游标就处于两组数组的中间。然后依次对前后两组数据排序，此时当然可以利用递归了。时间平均复杂度是O(n*logn)，排序算法貌似是公认最实用最好的排序算法，在大多数情况下都能解决问题，提高效率，当然也有糟糕的时候，此时的算法时间复杂度达到O(n2)。
6 归并排序
归并排序的思想就是把数组分成两组，前后两组分别排序，两组排完序后再把两组合并起来，当然可以利用递归的思想来实现归并排序，算法时间复杂度是O(n*logn)。
7 堆排序
首先说明什么是堆，堆其实就一个二叉树，其中要满足父节点大于或者小于子节点。把数组中元素按照堆来遍历，修正堆后，那么最大或者最小的元素就在根节点上了。我们把根节点移除，按照相同的方法再次得到最值，依次类推，直到剩下一个元素位置。算法时间复杂度是O(n*logn)。
8 基数排序
基数排序和后面要说的计数排序，桶排序都是非比较排序，因此他们能够突破比较排序的时间上限O(n*logn)，达到时间复杂度为)O(n)的程度，但是这几种排序都有限制性条件，不能看到他们的时间复杂付貌似比别的低一个等级就觉得他们是最好的排序算法了。三者的思想类似，都是用到了桶的概念。基数排序针对的是非负整数，将所有的数字依次比较个位，十位，百位，直到最高位，每一次比较都能得到一个排序，由于越往高位，这个位上数字影响权重越大，所以能够起到对前面顺序的修正。
9 计数排序
计数排序的思想也很简单，就是针对所有的整数。取一个从最小值到最大值的间隔，然后遍历数组，把当前元素放在下标为（当前元素值 - 最小值）的位置。是不是很简单啊，编程玩的就是思想，没有思想的程序员就不是真正的程序员。
10 桶排序
说到最后最后终于说到桶排序了。桶排序的思想就是先把数据分成一个个分组，这一个个分组就是一个个桶，当然这些桶是有顺序的，要不然桶排序作为非比较排序算法，连唯一的顺序都没有并且也不比较还排什么序啊。对于首次分桶后的数据可以采用递归或者其他的排序算法实现对每个桶内数据排序。最后按照桶号将所有数据依次连接就是拍完顺序的数据了。
二算法实现
常言道光说不练假把式，这里肯定要把实现代码贴出来了。
1 选择排序

void selectsort(int *pData,int left,int right)
{
int i,j,temp;
int tb;
for(i=left;i<right-1;i++)
{
temp = i;
for(j=i+1;j<right;j++)
{
if(pData[j]<pData[temp])
{
temp = j;
}
}
if(i != temp )
{
tb = pData[temp];
pData[temp] = pData[i];
pData[i] = tb;
}
}
}

复制代码

2 冒泡排序

void bubblesort(int *pData,int left,int right)
{
int i,j;
int temp;
for(i=left;i<right-1;i++)
{
for(j=left;j<right-i-1;j++)
{
if(pData[j+1]<pData[j])
{
temp = pData[j+1];
pData[j+1] = pData[j];
pData[j] = temp;
}
}
}
}

复制代码

3 插入排序

void insertsort(int *pData,int left,int right)
{
int i,j;
int temp;
for(i=left+1;i<right;i++)
{
temp = pData[i];
j = i;
while(--j>=left && pData[j]>temp)
{
pData[j+1] = pData[j];
}
pData[j+1] =temp;
}
}

复制代码

4 希尔排序

void shellsort(int *pData,int left,int right)
{
int i,j,gap;
int temp;
for(gap=right/2;gap>0;gap/=2)
{
for(i=gap;i<right;i++)
{
temp = pData[i];
for(j=i-gap;(j>=0)&&pData[j]>temp;j-=gap)
{
pData[j+gap] = pData[j];
}
pData[j+gap] = temp;
}
}
}

复制代码

5 快速排序三种实现方式
（1）游标为最左边元素

void quicksort(int *pData,int left,int right)
{
int i,j,middle,temp;
middle = pData[left];
i = left + 1;
j = right - 1;
do
{
while( i<right && pData[i]<middle)
i++;
while( j>left && pData[j]>middle)
j--;
if(i >= j)
break;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
i++;
j--;
}while(i<=j);
pData[left] = pData[j];
pData[j] = middle;
if(left<j-1)
quicksort(pData,left,j);
if(right>j+1)
quicksort(pData,j+1,right);
}

复制代码

（2）游标为中间元素

void quicksort2(int *pData,int left,int right)
{
int i,j,middle,temp;
i = left;
j = right - 1;
middle = pData[(i + j)/2];
do
{
while(i<right && pData[i]<middle)
i++;
while(j>left && pData[j]>middle)
j--;
if(i>=j)
break;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
i++;
j--;
}while(i<j);
if(left<i-1)
quicksort2(pData,left,i);
if(right>i+2)
quicksort2(pData,i,right);
}

复制代码

（3）游标为最后元素

void quicksort3(int *pData,int left,int right)
{
int i,j,last;
int temp,end;
i = left;
j = left;
last = right - 1;
end = pData[last];
//分配初始的i，j
if(pData[left]<end)
{
while( pData[++j]<end );
if(j == last)
{
quicksort3(pData,left,right-1);
return;
}
else
{
i = j-1;
}
}
else
{
while( pData[++j]>end );
temp = pData[j];
pData[j] = pData[left];
pData[left] = temp;
if(j == last)
{
quicksort3(pData,left+1,right);
return;
}
}
//分治排序
while(j<last-1)
{
j++;
if(pData[j]<end)
{
temp = pData[j];
pData[j] = pData[++i];
pData[i] = temp;
}
}
temp = end;
pData[last] = pData[i+1];
pData[i+1] = temp;
if(left<i)
quicksort3(pData,left,i+1);
if(right>i+3)
quicksort3(pData,i+2,right);
}

复制代码

6 归并排序
（1）递归法实现

void mergesort2(int *pData,int *Des,int left,int right)
{
int first = left;
int last = right-1;
if(first<last)
{
int mid = (first + last)/2;
mergesort2(pData,Des,first,mid+1);
mergesort2(pData,Des,mid+1,right);
merges(pData,Des,first,mid,last);
}
}
void merges(int *pData,int *Des,int first,int mid,int last)
{
int i = first;
int j = mid + 1;
int k = first;
while(i<=mid&&j<=last)
{
if(pData[i]<pData[j])
Des[k++] = pData[i++];
else
Des[k++] = pData[j++];
}
while(i<=mid)
{
Des[k++] = pData[i++];
}
while(j<=last)
{
Des[k++] = pData[j++];
}
for(k=first;k<=last;k++)
pData[k] = Des[k];
}

复制代码

（2）非递归法实现

void mergesort3(int *list,int length)
{
int i, left_min, left_max, right_min, right_max, next;
int *tmp = (int*)malloc(sizeof(int) * length);
if (tmp == NULL)
{
fputs("Error: out of memory\n", stderr);
abort();
}
for (i = 1; i < length; i *= 2)
{
for (left_min = 0; left_min < length - i; left_min = right_max)
{
right_min = left_max = left_min + i;
right_max = left_max + i;
if (right_max > length)
right_max = length;
next = 0;
while (left_min < left_max && right_min < right_max)
tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];
while (left_min < left_max)
list[--right_min] = list[--left_max];
while (next > 0)
list[--right_min] = tmp[--next];
}
}
free(tmp);
}

复制代码

7 堆排序

void HeapAdjust(int array[], int i, int nLength)
{
int nchild;
int ntemp;
while(i>=0)
{
nchild = 2 * i + 1;
ntemp = array[i];
if (array[nchild]<ntemp)
{
ntemp = array[nchild];
array[nchild] = array[i];
array[i] = ntemp;
}
if (nchild < nLength - 1)
{
nchild++;
if (array[nchild]<ntemp)
{
ntemp = array[nchild];
array[nchild] = array[i];
array[i] = ntemp;
}
}
i--;
}
}
// 堆排序算法
void HeapSort(int array[],int length)
{
int i,temp;
for (int nL = length; nL>0;nL--)
{
i = nL/2 - 1;
HeapAdjust(array,i,nL);
temp = array[0];
array[0] = array[nL-1];
array[nL-1] = temp;
}
}

复制代码

8 基数排序

#include <iostream>
using namespace std;
const int base=10;
struct wx
{
int num;
wx *next;
wx()
{
next=NULL;
}
};
wx *headn,*curn,*box[base],*curbox[base];
void basesort(int t)
{
int i,k=1,r,bn;
// k,r 分别表示10的幂次方，用来得到相应位上的单个数字，比如 k=10，r=100，数字207，则十位上 0 = //(207/r)%10
for(i=1;i<=t;i++)
{
k*=base;
}
r=k*base;
//curbox和box中的指针指向相同的位置，当curbox中有新元素时，curbox指向会发生变化，形成box元素为//头指针，curbox元素相当于滑动指针，这样可以通过比较两者的不同来判断指针的走向。
for(i=0;i<base;i++)
{
curbox[i]=box[i];
}
for(curn=headn->next;curn!=NULL;curn=curn->next)
{
bn=(curn->num%r)/k; // bn表示元素相应位上的值，
curbox[bn]->next=curn; //curbox[i]的next指向相应位为i的元素
curbox[bn]=curbox[bn]->next; //此时curbox[i]向后移位，以box[i]为首的链表长度增加
}
curn=headn;
for(i=0;i<base;i++)
{
if(curbox[i]!=box[i])
{
curn->next=box[i]->next;
curn=curbox[i]; //curn此时指向了在box中具有相同值的链表的最后一个，例如 123， //33，783，67，56，在3开头的元素链表中，此时cur指向了783。
}
}
curn->next=NULL;
}
void printwx()
{
for(curn=headn->next;curn!=NULL;curn=curn->next)
{
cout<<curn->num<<' ';
}
cout<<endl;
}
int main()
{
int i,n,z=0,maxn=0;
curn=headn=new wx;
cin>>n;
for(i=0;i<base;i++)
{
curbox[i]=box[i]=new wx;
}
for(i=1;i<=n;i++)
{
curn=curn->next=new wx;
cin>>curn->num;
maxn=max(maxn,curn->num);
}
while(maxn/base>0)
{
maxn/=base;
z++;
}
for(i=0;i<=z;i++)
{
basesort(i);
}
printwx();
return 0;
}

复制代码

9 计数排序

void CountSort(int array[],int nLength)
{
int nMin,nMax;
nMin = INT_MAX;
nMax = 0;
for(int i=0;i<nLength;i++)
{
if (nMax<array[i])
nMax = array[i];
if (nMin>array[i])
nMin = array[i];
}
int nSize = nMax - nMin + 1;
int *Count = NULL;
int *Sort = NULL;
Count = (int *)malloc( sizeof(int) * nSize );
Sort = (int *)malloc( sizeof(int) * nLength);
int j;
for (j=0;j<nSize;j++)
{
Count[j] = 0;
}
for (j=0;j<nLength;j++)
{
Count[array[j] - nMin]++;
}
for (j=0;j<nSize-1;j++)
{
Count[j+1] += Count[j];
}
for (j=nLength-1;j>=0;j--)
{
Sort[Count[ array[j]-nMin] -1 ] = array[j];
Count[array[j] - nMin]--;
}
for (j=0;j<nLength;j++)
{
array[j] = Sort[j];
}
free(Count);
free(Sort);
}

复制代码

10 桶排序

//文件1
#ifndef D_BUCKET_H
#define D_BUCKET_H
#include<cstdlib>
#include<climits>
using namespace std;
void BucketSort(int array[],int nLength,int nDivide);
struct bucket
{
int key;
bucket *next;
};
#endif
//文件2
#include"bucket.h"
void BucketSort(int arr[],int nLength,int nDivide)
{
bucket **Box = (bucket**)malloc( sizeof(bucket*) * nDivide );
for(int i =0;i<nDivide;i++)
{
Box[i] = (bucket*)malloc( sizeof(bucket) );
Box[i]->key = 0;
Box[i]->next = NULL;
}
// Find the Max and Min in the array
int nMin = INT_MAX;
int nMax = INT_MIN;
int nPie,nLeft;
for(int i = 0;i<nLength;i++)
{
nMin = (nMin<arr[i])?nMin:arr[i];
nMax = (nMax>arr[i])?nMax:arr[i];
}
nLeft = (nMax - nMin + 1) % nDivide;
if(nLeft == 0)
nPie = (nMax - nMin + 1) / nDivide;
else
nPie = (nMax - nMin + 1) /(nDivide - 1);
//Insert the element in bucket
for(int i = 0;i<nLength;i++)
{
bucket *node = (bucket*)malloc(sizeof(bucket));
node->key = arr[i];
node->next = NULL;
int nId = (arr[i] - nMin) / nPie;
if(Box[nId]->key == 0)
{
Box[nId]->next = node;
Box[nId]->key++;
}
else
{
bucket *p = Box[nId]->next;
bucket *cur = Box[nId];
while(p!=NULL && p->key < arr[i])
{
cur = p;
p = p->next;
}
cur->next = node;
node->next = p;
Box[nId]->key++;
}
}
// put the element in the array and also free the memory
int j = 0;
for(int i = 0;i<nDivide;i++)
{
bucket *pt = Box[i]->next;
bucket *cur = Box[i];
while(pt != NULL)
{
arr[j] = pt->key;
j++;
cur = pt;
pt = pt->next;
free(cur);
}
free(Box[i]);
}
free(Box);
}
//文件3
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#ifdef _DEBUG
#define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
#define new DEBUG_NEW
#endif
#include"bucket.h"
#include <iostream>
#include <string>
using namespace std;
const int NUM = 7;
const int DIV = 10;
void main()
{
int arr[NUM] = {69,78,99,12,34,56,45};
std::cout<<"Before sorting :\n";
for(int i=0;i<NUM;i++)
{
std::cout<<arr[i]<<" ";
}
std::cout<<endl;
BucketSort(arr,NUM,DIV);
std::cout<<"After sorting :\n";
for(int i=0;i<NUM;i++)
{
std::cout<<arr[i]<<" ";
}
//This is test whether has a memory leak
_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
}

复制代码

cyycoish · 发表于 2015-1-15 20:46:47

好！{:soso_e102:}我也会出我的算法数据结构教程{:soso_e121:}

元始天尊 · 发表于 2015-1-15 20:58:50

这个我已经写过啦http://www.0xaa55.com/forum.php? ... ;tid=739&extra=

账号		自动登录	找回密码
密码			立即注册→加入我们

【算法】十大排序算法

欢迎访问技术宅的结界，请注册或者登录吧。

相关帖子