各种排序算法

原博客老文章，转载自哪里也没写。

冒泡排序
　　
　　基本思想:
　　
　　先取第一个元素,将它与后面n-1个元素比较,将n个元素中最小的移到首部.
　　接着,忽略第一个元素,取第二个元素,将它与后面的n-2个元素比较,将n-1个
　　元素中最小的移到位置2.依此类推,直至第n个元素.
　　
　　1.list->r[1..n]
　　2.for i:1 to n do
　　3.for j:i to n do
　　4.if r[i]>r[j] then
　　5.swap(r[i],r[j])
　　6.end if
　　7.end for
　　8.end for
　　
　　源代码:
　　
　　void Bubble_Sort(int r[],int start,int end)
　　{
　　 int i,j;
　　 for(i=start;i<=end;i++)
　　 {
　　 for(j=i;j<=end;j++)
　　 {
　　 if(r[i]>r[j])
　　 {
　　 swap(&r[i],&r[j]);
　　 }
　　 }
　　 }
　　}
　　
　　选择排序
　　
　　基本思想:
　　
　　对待排序的记录序列进行n-1遍处理,第i遍处理将r[i..n]中最小的元素与r[i]
　　将换.这样,i遍处理后,前i个元素已经是正确的了.
　　
　　1.list->r[1..n]
　　2.for i:1 to n-1 do
　　3.minpos:=i
　　4.for j:i to n do
　　5.if r[j]　　6.minpos:=j
　　7.end if
　　8.end for
　　9.swap(r[i],r[minpos])
　　10.end for
　　
　　源代码:
　　
　　void Selection_Sort(int r[],int start,int end)
　　{
　　 int i,j,minpos;
　　 for(i=start;i<=end-1;i++)
　　 {
　　 minpos=i;
　　 for(j=i;j<=end;j++)
　　 {
　　 if(r[j]　　 {
　　 minpos=j;
　　 }
　　 }
　　 swap(&r[i],&r[minpos]);
　　 }
　　}
　　
　　插入排序
　　
　　基本思想:
　　
　　经过i-1遍处理后,r[1..i-1]已排好序.第i遍处理仅将r[i]插入到r[1..i-1]中的
　　合适位置,使得r[1..i]又是排好序的序列.要达到这个目的,我们可以利用第i-1遍
　　处理后r[1..i-1]已经排好序这个道理.在第i遍处理时,自上而下比较r[1..i-1],如
　　果发现r[i]>=r[i-1],那么r[1..i]排好序了,否则交换r[i]与r[i-1],继续这个过程.
　　直到r[i]找到一个合适的位置.
　　
　　1.list->r[1..n]
　　2.for i:2 to n do
　　3.for j:i-1 to 1 do
　　4.if r[j+1]　　5.swap(r[j+1],r[j])
　　6.else r[j+1]>=r[j]
　　7.break
　　8.end if
　　9.end for
　　10.end for
　　
　　源代码:
　　
　　void Insertion_Sort(int r[],int start,int end)
　　{
　　 int i,j;
　　 for(i=start+1;i<=end;i++)
　　 {
　　 for(j=i-1;j>=start;j--)
　　 {
　　 if(r[j+1]　　 {
　　 swap(&r[j+1],&r[j]);
　　 }
　　 else
　　 break;
　　 }
　　 }
　　}
　　
　　堆排序
　　
　　基本思想:
　　
　　堆这种数据结构是满足下列性质的序列r[1..n]:r[i]<=r[2*i],r[i]<=r[2*i+1];
　　or r[i]>=r[2*i],r[i]>=r[2*i+1](i<=(n/2)).从逻辑上看,一个堆事实上可以表达为
　　一棵二叉树,这棵树的父节点总比它的两个(或只有一个)子节点或者大或者小.根据大
　　或者小的性质,堆可以分为大根堆和小根堆.大根堆中根节点最大,小根堆中根节点最小.
　　利用堆的这种性质,我们将数列r[1..n]建成一个大根堆.然后将r[1]与r[n]交换,这样,
　　r[n]是最大的,接着调整r[1..n-1]为堆,再交换r[1]跟r[n-1],依此类推.
　　
　　1.list->r[1..n]
　　2.BuildHeap(r[1..n])
　　3.for i:n to 2 do
　　4.swap(r[1],r[i])
　　5.ModifyHeap(r[1..i-1])
　　6.end for
　　
　　ModifyHeap的实现思想
　　
　　以调整r[low..high]为例.此时r[row]为根节点,根据堆的性质,所有子树也构成堆.所以,
　　我们可以知道,r[low]下的两棵子树其实也是堆.于是,我们将r[low]与它两个子节点中较
　　大的那个交换(当然,如果r[low]比它的两个子节点都大,那么r[low..high]本身已经是一个
　　堆了),交换后,对新构成的子树做相同操作,依此类推.我们可以得到一个调整后的新堆.
　　
　　1.list->r[1..n]
　　2.curpos:=1;
　　3.while curpos<(n/2)+1
　　4.if 2*curpos+1>n then
　　5.if r[curpos]　　6.swap(r[curpos],r[2*curpos])
　　7.return
　　8.else
　　9.return
　　10.end if
　　11.end if
　　12.if r[curpos]　　13.if r[2*curpos]>r[2*curpos+1] then
　　14.swap(r[curpos],r[2*curpos])
　　15.curpos:=2*curpos
　　16.else
　　17.swap(r[curpos,r[2*curpos+1])
　　18.curpos:=2*curpos+1
　　19.end if
　　20.end if
　　21.end while
　　
　　BuildHeap的实现思想
　　
　　BuildHeap事实上借用了ModifyHeap的思想,我们只要依次将不是叶节点(叶节点本身已是
　　一个堆)的节点按顺序从大到小利用ModifyHeap调整为堆即可.
　　
　　1.list->r[1..n]
　　2.for i:(n/2)+1 to 1 do
　　3.ModifyHeap(r,i,n)
　　4.end for
　　
　　源代码:
　　
　　void ModifyHeap(int r[],int start,int end)
　　{
　　 int curpos=start,maxnum;
　　 while(curpos+1<(((end+1)/2)+1)) /* array begin with 0 */
　　 {
　　 if(2*(curpos+1)+1>(end+1))
　　 {
　　 if(r[curpos]　　 {
　　 swap(&r[curpos],&r[2*curpos+1]);
　　 return;
　　 }
　　 else
　　 return;
　　 }
　　 maxnum=max(r[2*curpos+1],r[2*curpos+2]);
　　 if(r[curpos]　　 {
　　 if(r[2*curpos+1]>r[2*curpos+2])
　　 {
　　 swap(&r[curpos],&r[2*curpos+1]);
　　 curpos=2*curpos+1;
　　 }
　　 else
　　 {
　　 swap(&r[curpos],&r[2*curpos+2]);
　　 curpos=2*curpos+2;
　　 }
　　 }
　　 else
　　 {
　　 return;
　　 }
　　 }
　　}
　　
　　void BuildHeap(int r[],int start,int end)
　　{
　　 int i;
　　 for(i=(start+end)/2;i>=start;i--)
　　 {
　　 ModifyHeap(r,i,end);
　　 }
　　}
　　
　　void Heap_Sort(int r[],int start,int end)
　　{
　　 int i;
　　 BuildHeap(r,start,end);
　　 for(i=end;i>start;i--)
　　 {
　　 swap(&r[start],&r[i]);
　　 ModifyHeap(r,start,i-1);
　　 }
　　}
　　
　　
　　快速排序
　　
　　基本思想:
　　
　　快速排序的基本思想是基于分治策略的.对于输入的子序列r[p..r],如果规模足够小则直
　　接进行排序,否则分三步处理:
　　
　　分解:将输入的序列r[p..r]划分成两个非空子序列r[p..q]和r[q+1..r],使r[p..q]中任一
　　元素的值不大于r[q+1,r]中任一元素的值.
　　递归求解:通过递归调用快速排序算法分别对r[p..q]和r[q+1..r]进行排序.
　　合并:由于对分解出的两个子序列的排序是就地进行的,所以在r[p..q]和r[q+1..r]都排好
　　序后不需要执行任务计算r[p..r]就已排好序.
　　
　　1.list->r[1..n]
　　2.if n-1<=12 then
　　3.insertion_sort(r,p,h)
　　4.return
　　5.end if
　　6.q:=partition(p,h,r)
　　7.Quick_Sort(p,q,r)
　　8.Quick_Sort(q+1,h,r)
　　
　　partition实现思想
　　
　　1.在r[p..h]中选择一个支点元素pivot(随机选择的平均性能最好)
　　2.对r[p..h]中的元素进行整理,使得r[p..h]分为两部分r[p..q]和r[q+1..h],并且r[p..q]
　　中的每一个元素的值不大于pivot,r[q+1..h]中的每一个元素的值不小于pivot,r[p..q]和
　　r[q+1..h]中的元素并不要求排好序.
　　
　　1.list->r[1..n]
　　2.position:=(n+1)/2
　　3.pivot:=r[position]
　　4.for i:1 to n do
　　5.if i　　6.if r[i]>pivot then
　　7.tmpstore:=r[i]
　　8.for j:i+1 to position do
　　9.r[j-1]=r[j]
　　10.end for
　　11.r[position]=tmpstore
　　12.position:=position-1
　　13.end if
　　14.end if
　　15.if i>position then
　　16.if r[i]　　17.tmpstore:=r[i]
　　18.for m:position to i-1 do
　　19.r[m+1]:=r[m]
　　20.end for
　　21.r[position]:=tmpstore
　　22.position:=position+1
　　23.end if
　　24.end if
　　25.end for
　　
　　源代码:
　　
　　int Partition(int r[],int start,int end)
　　{
　　 int i,j,m,position,pivot,tmpstore;
　　 position=(start+end)/2;
　　 pivot=r[position];
　　 printf("\n\n%d %d\n",position,pivot);
　　 for(i=start;i<=end;i++)
　　 {
　　 if(i　　 {
　　 if(r[i]>pivot)
　　 {
　　 tmpstore=r[i];
　　 for(j=i+1;j<=position;j++)
　　 {
　　 r[j-1]=r[j];
　　 }
　　 r[position]=tmpstore;
　　 position=position-1;
　　 i--; /* in case of two continuous larger number */
　　 }
　　 }
　　 else if(i>position)
　　 {
　　 if(r[i]　　 {
　　 tmpstore=r[i];
　　 for(m=i-1;m>=position;m--)
　　 {
　　 r[m+1]=r[m];
　　 }
　　 r[position]=tmpstore;
　　 position=position+1;
　　 }
　　 }
　　 }
　　 return position;
　　}
　　
　　void Quick_Sort(int r[],int start,int end)
　　{
　　 int q;
　　
　　 if(end-start<=12)
　　 {
　　 Insertion_Sort(r,start,end);
　　 return;
　　 }
　　
　　 q=Partition(r,start,end);
　　 Quick_Sort(r,start,q);
　　 Quick_Sort(r,q+1,end);
　　}
　　
　　若只算时间复杂度,以快速排序和堆排序为佳.为O(nlogn).