排序.docx

排序.docx

《排序.docx》由会员分享，可在线阅读，更多相关《排序.docx（25页珍藏版）》请在冰点文库上搜索。

排序

排序小结

　　本文介绍的排序算法有：

冒泡排序，选择排序，插入排序，归并排序，希尔排序，堆排序，快速排序，计数排序，基数排序，桶排序。

包括定义描述、排序过程、复杂度和代码实现（如有错误，请指正Thanks）。

概念：

∙排序稳定：

如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。

∙原地排序：

原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。

例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。

冒泡排序[BubbleSort]

　　依次比较相邻的两个数，将小数放在前面，大数放在后面。

   复杂度：

       最差时间复杂度[O（n^2）],最优时间复杂度[O（n）],平均时间复杂度[O（n^2）],最差空间复杂度[O（n）total,O

（1）auxiliary]

 　　代码：

　　　　C#版

1publicstaticvoidBubbleSort（int[]arr）

2{

3//[flag]{true=>itemexchanged;false=>noitemexchanged}

4boolflag;

5inttemp;

6

7for（inti=0;i

8{

9flag=false;

10for（intj=0;j

11{

12if（arr[j]>arr[j+1]）

13{

14temp=arr[j];

15arr[j]=arr[j+1];

16arr[j+1]=temp;

17flag=true;

18}

19}

20if（flag==false）

21{

22break;

23}

24}

25}

　　　　C版

1voidbubbleSort（int*arr,intn）

2{

3inti,j,flag,temp;

4for（i=0;i

5{

6flag=0;

7for（j=0;j

8{

9if（arr[j]>arr[j+1]）

10{

11temp=arr[j];

12arr[j]=arr[j+1];

13arr[j+1]=temp;

14flag=1;

15}

16}

17if（flag==0）

18{

19break;

20}

21}

22}

选择排序[SelectionSort]

　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

   复杂度：

       最差时间复杂度[O（n^2）],最优时间复杂度[O（n^2）],平均时间复杂度[O（n^2）],最差空间复杂度[O（n）total,O

（1）auxiliary]

 　　代码：

　　　　C#版

1publicstaticvoidSelectionSort（int[]arr）

2{

3intminIndex;

4intminValue;

5inttemp;

6

7for（inti=0;i

8{

9minValue=arr[i];

10minIndex=i;

11for（intj=i+1;j

12{

13if（arr[j]

14{

15minValue=arr[j];

16minIndex=j;

17}

18}

19if（minIndex!

=i&&minValue!

=arr[i]）

20{

21temp=arr[i];

22arr[i]=arr[minIndex];

23arr[minIndex]=temp;

24}

25}

26}

　　　　C版

1voidselectionSort（int*arr,intn）

2{

3intminIndex,minValue,temp;

4inti,j;

5

6for（i=0;i

7{

8minIndex=i;

9minValue=arr[i];

10for（j=i+1;j

11{

12if（arr[j]

13{

14minIndex=j;

15minValue=arr[j];

16}

17}

18if（minIndex!

=i&&minValue!

=arr[i]）

19{

20temp=arr[i];

21arr[i]=minValue;

22arr[minIndex]=temp;

23}

24}

25}

插入排序[InsertionSort]

　　将n个元素的数列分为已有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

   复杂度：

       最差时间复杂度[O（n^2）],最优时间复杂度[O（n^2）],平均时间复杂度[O（n^2）],最差空间复杂度[O（n）total,O

（1）auxiliary]

 　　代码：

　　　　C#版

1publicstaticvoidInsertionSort（int[]arr）

2{

3inttemp;

4intj;

5for（inti=1;i

6{

7temp=arr[i];

8for（j=i-1;j>-1;j--）

9{

10if（temp

11{

12arr[j+1]=arr[j];

13}

14else

15{

16break;

17}

18}

19arr[j+1]=temp;

20}

21}

　　　　C版

1voidinsertionSort（int*arr,intn）

2{

3inti,j,temp;

4

5for（i=1;i

6{

7temp=arr[i];

8for（j=i-1;j>-1;j--）

9{

10if（temp

11{

12arr[j+1]=arr[j];

13}

14else

15{

16break;

17}

18}

19arr[j+1]=temp;

20}

21}

归并排序[MergeSort]

　　将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。

然后再把有序子序列合并为整体有序序列。

   排序过程如下：

   　　1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

   　　2）设定两个指针，最初位置分别为两个已经排序序列的起始位置

   　　3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

   　　4）重复步骤3直到某一指针达到序列尾

   　　5）将另一序列剩下的所有元素直接复制到合并序列尾

   复杂度：

       最差时间复杂度[O（nlogn）],最优时间复杂度[O（n）],平均时间复杂度[O（nlogn）],最差空间复杂度[O（n）]

 　　代码：

　　　　C#版

1publicstaticvoidMergeSort（int[]arr,intstart,intend）

2{

3if（start

4{

5intmid=（start+end）/2;

6MergeSort（arr,start,mid）;

7MergeSort（arr,mid+1,end）;

8Merge（arr,start,mid,end）;

9}

10}

11publicstaticvoidMerge（int[]arr,intstart,intmid,intend）

12{

13int[]temp=newint[end-start+1];

14inti=start;

15intj=mid+1;

16intk=0;

17while（i<=mid&&j<=end）

18{

19if（arr[i]

20{

21temp[k++]=arr[i++];

22}

23else

24{

25temp[k++]=arr[j++];

26}

27}

28while（i<=mid）

29{

30temp[k++]=arr[i++];

31}

32while（j<=end）

33{

34temp[k++]=arr[j++];

35}

36for（k=0,i=start;k

37{

38arr[i]=temp[k];

39}

40}

　　　　C版

1voidmergeSort（int*arr,intn）

2{

3if（n>1）

4{

5intmid=n/2;

6mergeSort（arr,mid）;

7mergeSort（arr+mid,n-mid）;

8merge（arr,n,mid-1）;

9}

10}

11voidmerge（int*arr,intn,intmid）

12{

13int*temp=malloc（n*sizeof（int））;

14inti=0;

15intj=mid+1;

16intk=0;

17

18while（i<=mid&&j

19{

20if（arr[i]

21{

22temp[k++]=arr[i++];

23}

24else

25{

26temp[k++]=arr[j++];

27}

28}

29while（i<=mid）

30{

31temp[k++]=arr[i++];

32}

33while（j

34{

35temp[k++]=arr[j++];

36}

37

38for（k=0;k

39{

40arr[k]=temp[k];

41}

42free（temp）;

43}

希尔排序[ShellSort]

　　希尔排序插入排序的一种，是针对直接插入排序算法的改进，该方法又称缩小增量排序。

   排序过程如下：

   　　1）取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中

   　　2）在各组内进行直接插入排序

   　　3）取第二个增量d2

   复杂度：

       最差时间复杂度[O（n^s）1

（1）]

 　　代码：

　　　　C#版

1publicstaticvoidShellSort（int[]arr）

2{

3intd=arr.Length/2;

4inttemp,j;

5

6while（d>0）

7{

8for（inti=1;i

9{

10temp=arr[i];

11for（j=i-d;j>=0;j-=d）

12{

13if（arr[j]>temp）

14{

15arr[j+d]=arr[j];

16}

17else

18{

19break;

20}

21}

22arr[j+d]=temp;

23}

24d/=2;

25}

26}

　　　　C版

1voidshellSort（int*arr,intn）

2{

3intd=n/2;

4inti,j,temp;

5

6while（d>0）

7{

8for（i=1;i

9{

10temp=arr[i];

11for（j=i-d;j>=0;j-=d）

12{

13if（arr[j]>temp）

14{

15arr[j+d]=arr[j];

16}

17else

18{

19break;

20}

21}

22arr[j+d]=temp;

23}

24d/=2;

25}

26}

堆排序[HeapSort]

　　堆积排序是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

   排序过程如下：

   　　1）建立一个堆H[0..n-1]

   　　2）把堆首（最大值）和堆尾互换

   　　3）把堆的尺寸缩小1，并调用shift_down（0）,目的是把新的数组顶端数据调整到相应位置

   　　4）重复步骤2，直到堆的尺寸为1

   复杂度：

       最差时间复杂度[O（nlogn）],最优时间复杂度[O（nlogn）],平均时间复杂度[O（nlogn）],最差空间复杂度[O（n）total,O

（1）auxiliary]   

 　　代码：

　　　　C#版

1publicstaticvoidHeapSort（int[]arr）

2{

3BuildMaxHeap（arr）;

4

5for（inti=arr.Length-1;i>0;i--）

6{

7Swap（refarr[0],refarr[i]）;//将堆顶元素和无序区的最后一个元素交换

8MaxHeaping（arr,0,i）;//将新的无序区调整为堆

9}

10}

11///

15privatestaticvoidBuildMaxHeap（int[]arr）

16{

17for（inti=arr.Length/2-1;i>=0;i--）

18{

19MaxHeaping（arr,i,arr.Length）;

20}

21}

22///

25///需要调整的节点

26///堆的大小，也指数组中无序区的长度

27privatestaticvoidMaxHeaping（int[]arr,inti,intheapSize）

28{

29intleft=2*i+1;

30intright=2*i+2;

31intlarge=i;//存放大的节点

32

33if（leftarr[large]）

34{

35large=left;

36}

37if（rightarr[large]）

38{

39large=right;

40}

41//如有子节点大于自身就交换，使值大的元素上移

42if（i!

=large）

43{

44Swap（refarr[i],refarr[large]）;

45MaxHeaping（arr,i,heapSize）;

46}

47}

48privatestaticvoidSwap（refinta,refintb）

49{

50inttemp=a;

51a=b;

52b=temp;

53}

　　　　C版

1voidheapSort（int*arr,intn）

2{

3inti;

4buildMaxHeap（arr,n）;

5

6for（i=n-1;i>0;i--）

7{

8swap（arr,arr+i）;

9maxHeaping（arr,0,i）;

10}

11}

12voidbuildMaxHeap（int*arr,intn）

13{

14inti;

15for（i=n/2-1;i>=0;i--）

16{

17maxHeaping（arr,i,n）;

18}

19}

20voidmaxHeaping（int*arr,inti,intheapsize）

21{

22intleft=2*i+1;

23intright=2*i+2;

24intlarge=i;

25

26if（leftarr[large]）

27{

28large=left;

29}

30if（rightarr[large]）

31{

32large=right;

33}

34if（i!

=large）

35{

36swap（arr+i,arr+large）;

37maxHeaping（arr,large,heapsize）;

38}

39}

40voidswap（int*a,int*b）

41{

42inttemp=*a;

43*a=*b;

44*b=temp;

45}

快速排序[QuickSort]

　　通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

   排序过程如下：

   　　1）设置两个变量i、j，排序开始的时候：

i=0，j=n-1

   　　2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]

   　　3）从j开始向前搜索，即由后开始向前搜索（j=j-1），找到第一个小于key的值A[j]，并与A[i]交换

   　　4）从i开始向后搜索，即由前开始向后搜索（i=i+1），找到第一个大于key的A[i]，与A[j]交换

   　　5）重复第3、4、5步，直到i=j；（3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。

找到并交换的时候i，j指针位置不变。

另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。

）

   复杂度：

       最差时间复杂度[O（n^2）],最优时间复杂度[O（nlogn）],平均时间复杂度[O（nlogn）],最差空间复杂度[根据实现方式而定]  

 　　代码：

　　　　C#版

1publicstaticvoidQuickSort（int[]arr,intstart,intend）

2{

3if（end-start<=0）

4{

5return;

6}

7

8intlast=start;

9intrandIndex=newRandom（）.Next（start,end+1）;

10Swap（refarr[start],refarr[randIndex]）;

11for（inti=start+1;i<=end;i++）

12{

13if（arr[i]

14{

15Swap（refarr[++last],refarr[i]）;

16}

17}

18Swap（refarr[start],refarr[last]）;

19QuickSort（arr,start,last-1）;

20QuickSort（arr,last