黑马程序员技术交流社区

标题: 关于排序算法的总结 [打印本页]
作者: 菊花爆满山    时间: 2015-5-31 19:06
标题: 关于排序算法的总结
首先从最简单的冒泡排序  PS：有哪里不对的地方，请批评直言，望不吝赐教。
这里直接上代码
  1. void BubbleSort(int b[],int n)
  2. {
  3.         int temp,i,j,count1=0,count2=0;                              
  4.         for(i=0;i<n-1;i++)
  5.         {
  6.                 for(j=n-1;j>i;j--)
  7.                 {
  8.                         count1++;
  9.                         if(b[j-1]>b[j])
  10.                         {
  11.                                 count2++;
  12.                                 temp=b[j-1];
  13.                                 b[j-1]=b[j];
  14.                                 b[j]=temp;
  15.                         }
  16.                 }
  17.         }
  18. printf("一共进行了%d次比较,进行了%d次移动\n",count1,count2);

  20. }
  21. int main()
  22. {
  23.         int a[10]={9,4,12,15,2,7,11,21,25,3};
  24.         BubbleSort(a,10);
  25.         for(int i=0;i<10;i++)
  26.         {
  27.                 printf("%-2d ",a[i]);
  28.         }
  29.         printf("\n\n");
  30.         return 0;
  31. }
复制代码

上面的代码是从后往前两两比较  也可以从前往后两两比较 只要把两个for嵌套改一下就OK了！
  1.         for(i=0;i<n-1;i++)
  2.         {
  3.                 for(j=0;j<n-1-i;j++)
  4.                 {
  5.                         count1++;
  6.                         if(b[j]>b[j+1])
  7.                         {
  8.                                 count2++;
  9.                                 temp=b[j+1];
  10.                                 b[j+1]=b[j];
  11.                                 b[j]=temp;
  12.                         }
  13.                 }
  14.         }
复制代码

总结一下冒泡排序  如果有n个数 就要进行n-1趟 第j趟 就要进行n-1-j趟两两比较

关于冒泡排序的优化处理
直接上代码
  1. void BubbleSort(int b[],int n)
  2. {
  3.         int temp,i,j,count1=0,count2=0,flag;      
  4.         flag=1;                                 
  5.         for(i=0;i<n-1&&flag;i++)
  6.         {
  7.                 for(j=n-1;j>i;j--)
  8.                 {
  9.                         count1++;
  10.                         flag=0;
  11.                         if(b[j-1]>b[j])
  12.                         {
  13.                                 count2++;
  14.                                 temp=b[j-1];
  15.                                 b[j-1]=b[j];
  16.                                 b[j]=temp;
  17.                                 flag=1;
  18.                         }
  19.                 }
  20.         }
  21. printf("一共进行了%d次比较,进行了%d次移动\n",count1,count2);

  23. }
复制代码

这里是的优化 省去了不必要的比较 例如数组a[10]={1,0,2,3,4,5,6,7,8,9};当 i=0时 for循环后 排序变为 0 1 2 3 4 5 6 7 8 9 再当i=1时 发现后面的一个数总是大于前面的一个数 这里不进入内部for循环 因此直接跳出for循环 在比较上省去了很多步。

作者: 菊花爆满山    时间: 2015-5-31 19:26
选择排序算法
先上代码
  1. void SelectSort(int k[],int n)
  2. {
  3.         int i,j,temp,min,count1=0,count2=0;
  4.         for(i=0;i<n-1;i++)
  5.         {
  6.                 min=i;
  7.                 for(j=i+1;j<n;j++)
  8.                 {
  9.                         count1++;
  10.                         if(k[j]<k[min])
  11.                         {
  12.                                 min=j;
  13.                         }
  14.                 }

  16.                 if(min!=i)
  17.                 {
  18.                         count2++;
  19.                         temp=k[min];
  20.                         k[min]=k[i];
  21.                         k[i]=temp;
  22.                 }
  23.         }

  25.         printf("总共 进行了%d次比较 进行了%d次移动\n",count1,count2);
  26. }
复制代码

关于选择排序 依然是n-1趟 每进行一趟 就把最小的数放到i的位置上 例如数组a[10]={5,2,6,0,3,9,1,7,4,8};当i=0的时候 2与5比较 显然2的值小于5 这时min=1 再比较6大于2 则min值不做处理 再0的值小于2 这时min=3 以此类推 最后把最小的值的下标给了min 然后把K[min]与K进行交换 显然选择排序的移动次数要小于冒泡排序 这就体现在"选择"上。
作者: 菊花爆满山    时间: 2015-5-31 19:47
直接插入排序
上代码
  1. void InsertSort(int k[],int n)
  2. {
  3.         int i,j,temp;
  4.         for(i=1;i<n;i++)
  5.         {
  6.                 if(k[i]<k[i-1])
  7.                 {
  8.                         temp=k[i];         

  10.                         for(j=i-1;k[j]>temp;j--)
  11.                         {
  12.                                 k[j+1]=k[j];
  13.                         }
  14.                         k[j+1]=temp;
  15.                 }
  16.         }
  17. }
复制代码


关于直接插入排序
这里有两点是要注意的
第一：n的范围是1到n-1
第二：每次比较都是小于前继元素的元素依次与所有前继元素比较 直到它的前继元素大于它时 它就插入在该前继元素的后驱上
作者: 菊花爆满山    时间: 2015-5-31 20:01
前面3种排序都是简单的排序算法
接下来是复杂一点排序算法
希尔排序
希尔排序是从直接插入排序演变而来的
代码：
  1. void ShellSort(int k[],int n)
  2. {
  3.         int i,j,temp;
  4.         int gap=n;
  5.         do
  6.         {
  7.                 gap=gap/5+1;
  8.                 for(i=gap;i<n;i++)
  9.                 {
  10.                         if(k[i]<k[i-gap])
  11.                         {
  12.                                 temp=k[i];                  
  13.                                 for(j=i-gap;k[j]>temp;j-=gap)
  14.                                 {
  15.                                         k[j+gap]=k[j];
  16.                                 }
  17.                                 k[j+gap]=temp;
  18.                         }
  19.                 }
  20.         }while(gap>1);
  21. }
复制代码


希尔排序的实质其实就是分组插入排序  
将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
代码里的gap就是增量 当gap不大于1时 跳出循环。
作者: 菊花爆满山    时间: 2015-6-1 00:08
本帖最后由 菊花爆满山 于 2015-6-1 11:10 编辑

堆排序
代码:
  1. int count=0;
  2. void swap(int k[],int i,int j)
  3. {
  4.         int temp;
  5.         temp=k[i];
  6.         k[i]=k[j];
  7.         k[j]=temp;
  8. }
  9. void HeapAdjust(int k[],int s,int n)
  10. {
  11.         int i,temp;
  12.         temp=k[s];
  13.         for(i=2*s;i<=n;i*=2)
  14.         {
  15.                 count++;
  16.                 if(i<n&&k[i]<k[i+1])
  17.                 {
  18.                         i++;
  19.                 }

  21.                 if(temp>=k[i])
  22.                 {
  23.                         break;
  24.                 }
  25.                 k[s]=k[i];
  26.                 s=i;
  27.         }
  28.         k[s]=temp;
  29. }
  30. void HeapSort(int k[],int n)
  31. {
  32.         int i;
  33.         for(i=n/2;i>0;i--)
  34.         {
  35.                 HeapAdjust(k,i,n);
  36.         }

  38.         for(i=n;i>1;i--)
  39.         {
  40.                 swap(k,1,i);
  41.                 HeapAdjust(k,1,i-1);
  42.         }
  43. }
  44. int main()
  45. {
  46.         int a[10]={-1,5,2,6,0,3,9,1,7,4};  //元素从下标为1开始存放
  47.         HeapSort(a,9);

  49.         printf("总共进行了%d次比较!\n",count);
  50.         for(int i=1;i<10;i++)
  51.         {
  52.                 printf("%-2d ",a[i]);
  53.         }
  54.         printf("\n\n");
  55.         return 0;
  56. }
复制代码

关于推排序  首先要把给定数组变成一个大顶堆（从小到大排序）  小顶堆（从大到小排序）
例如 a[10]={-1,5,2,6,0,3,9,1,7,4};
它的层序遍历是
要转换为完全二叉树且父亲的值总是大于左右孩子的值 就构成了大顶堆
也就是代码中的HeapAdjust(k,i,n);这一步就是将数组转换为大顶堆




作者: 小苹果要上树了    时间: 2015-6-1 00:14
点赞，总结的不错，很好！
作者: 菊花爆满山    时间: 2015-6-1 00:48
本帖最后由 菊花爆满山 于 2015-6-1 00:51 编辑

这里主要说说HeapAdjust(k,i,n);函数
首先从最低层开始 按代码里的看 首先当i=9/2=4  所以temp=k[4]=0  然后找出父亲为0的孩子中最大的一个儿子 由上图可以看出是左孩子7
temp>k[8]=7,所以将k[4]=k[7]  s=8  然后再往下遍历(由于父亲为7没有孩子) 所以直接执行最后把temp的值给k  然后依次i=3 2 1 这里说一下i= 4和i=2如下图所示









作者: 菊花爆满山    时间: 2015-6-1 11:16
构成大顶堆后 再层序遍历是9 7 6 4 3 5 1 0 2 把第一个元素即（大顶堆的堆顶）与最后一个元素交换 这样最大值就跑到了最右边 然后再次把剩下的 2 7 6 4 3 5 1 0 构成新的大顶堆 依次做上述操作 就完成了从小到大的排序
作者: 菊花爆满山    时间: 2015-6-1 11:22
归并排序
代码：
  1. #define MAXSIZE 10
  2. void merging(int *list1,int list1_size,int *list2,int list2_size)
  3. {
  4.         int i,j,k,m;
  5.         i=j=k=0;
  6.         int temp[MAXSIZE];
  7.         while(i<list1_size&&j<list2_size)
  8.         {
  9.                 if(list1[i]<list2[j])
  10.                 {
  11.                         temp[k++]=list1[i++];
  12.                 }
  13.                 else
  14.                 {
  15.                         temp[k++]=list2[j++];
  16.                 }
  17.         }

  19.         while(i<list1_size)
  20.         {
  21.                 temp[k++]=list1[i++];
  22.         }

  24.         while(j<list2_size)
  25.         {
  26.                 temp[k++]=list2[j++];
  27.         }

  29.         for(m=0;m<(list1_size+list2_size);m++)   //实现归并 并把结果放到list1里
  30.         {
  31.                 list1[m]=temp[m];
  32.         }
  33. }
  34. void MergeSort(int k[],int n)
  35. {
  36.         if(n>1)
  37.         {
  38.                 int *list1=k;
  39.                 int list1_size=n/2;
  40.                 int *list2=k+n/2;
  41.                 int list2_size=n-list1_size;

  43.                 MergeSort(list1,list1_size);
  44.                 MergeSort(list2,list2_size);

  46.                 merging(list1,list1_size,list2,list2_size);

  48.         }
  49. }
  50. int main()
  51. {
  52.         int a[10]={5,2,6,0,3,9,1,7,4,8};
  53.         MergeSort(a,10);
  54.         for(int i=0;i<10;i++)
  55.         {
  56.                 printf("%-2d ",a[i]);
  57.         }
  58.         printf("\n\n");
  59.         return 0;
  60. }
复制代码
上面的代码是递归实现 同样也可以迭代实现 代码如下

  1. #define LEN 10

  3. void merge_sort(int *list, int length)
  4. {
  5.     int i, left_min, left_max, right_min, right_max, next;
  6.     int *tmp = (int*)malloc(sizeof(int) * length);

  8.     if (tmp == NULL)
  9.     {
  10.          fputs("Error: out of memory\n", stderr);
  11.         abort();
  12.      }

  14.     for (i = 1; i < length; i *= 2) // i为步长，1,2,4,8……
  15.     {
  16.          for (left_min = 0; left_min < length - i; left_min = right_max)
  17.        {
  18.             right_min = left_max = left_min + i;
  19.             right_max = left_max + i;

  21.            if (right_max > length)
  22.                 right_max = length;

  24.             next = 0;
  25.             while (left_min < left_max && right_min < right_max)
  26.                 tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];

  28.             while (left_min < left_max)
  29.                 list[--right_min] = list[--left_max];

  31.             while (next > 0)
  32.                  list[--right_min] = tmp[--next];
  33.          }
  34.      }

  36.     free(tmp);

  38. }


  41. int main(void)
  42. {
  43.      int a[LEN] = { 5, 2, 4, 7, 1, 3, 8, 6 ,9 ,0 };
  44.      merge_sort(a, LEN);
  45.      int i;
  46.      for (i = 0; i < LEN; i++)
  47.         printf("%d ", a[i]);
  48.          printf("\n");

  50.      return 0;
  51. }
复制代码





作者: 菊花爆满山    时间: 2015-6-1 12:02
这里就说一下递归的实现原理



原理很简单 也就是上图所示  先用递归实现分裂 然后再归并 递归的返回条件就是n=1  所以递归外部要if(n>1)做返回判断
这里主要说一下归并函数merging(list1,list1_size,list2,list2_size)


然后就是依次合并 最后形成一个有序的序列
作者: 菊花爆满山    时间: 2015-6-1 12:17
最后一个排序 快速排序
代码
  1. void swap(int k[],int low,int high)
  2. {
  3.         int temp;
  4.         temp=k[low];
  5.         k[low]=k[high];
  6.         k[high]=temp;
  7. }
  8. int Partition(int k[],int low,int high)
  9. {
  10.         int point;
  11.         point=k[low];
  12.         while(low<high)
  13.         {
  14.                 while(low<high&&k[high]>=point)
  15.                 {
  16.                         high--;
  17.                 }
  18.                 swap(k,low,high);

  20.                 while(low<high&&k[low]<=point)
  21.                 {
  22.                         low++;
  23.                 }
  24.                 swap(k,low,high);

  26.         }
  27.         return low;
  28. }
  29. void Quick(int k[],int low,int high)
  30. {
  31.         int point;
  32.         if(low<high)
  33.         {
  34.                 point=Partition(k,low,high);
  35.                 Quick(k,low,point-1);
  36.                 Quick(k,point+1,high);
  37.         }
  38. }
  39. void QuickSort(int k[],int n)
  40. {
  41.         Quick(k,0,n-1);
  42. }
  43. int main()
  44. {
  45.         int a[10]={5,2,6,0,3,9,1,7,4,8};
  46.         QuickSort(a,10);
  47.         for(int i=0;i<10;i++)
  48.         {
  49.                 printf("%-2d ",a[i]);
  50.         }
  51.         printf("\n\n");
  52.         return 0;
  53. }
复制代码

这个原理就很简单了
例如数组a[10]={5,2,6,0,3,9,1,7,4,8};
代码里一开始是第一个元素作为point 也就是5




作者: 菊花爆满山    时间: 2015-6-1 12:23
Partition(k,low,high)函数里面每次当low=high 的时候遍历一次结束  然后递归将序列分成两半 然后依次执行point=Partition(k,low,high)把中间点找到 然后再往下递归 当low=high时递归返回
作者: 菊花爆满山    时间: 2015-6-1 12:26
最后是优化后的快速排序算法代码
  1. #define MAX_LENGTH_SIZE 7

  3. void Insert(int k[],int n)      
  4. {
  5.         int i,j,temp;
  6.         for(i=1;i<n;i++)
  7.         {
  8.                 if(k[i]<k[i-1])
  9.                 {
  10.                         temp=k[i];         

  12.                         for(j=i-1;k[j]>temp;j--)
  13.                         {
  14.                                 k[j+1]=k[j];
  15.                         }
  16.                         k[j+1]=temp;
  17.                 }
  18.         }
  19. }

  21. void InsertSort(int k[],int low,int high)
  22. {
  23.         Insert(k+low,high-low+1);
  24. }

  26. void swap(int k[],int low,int high)
  27. {
  28.         int temp;
  29.         temp=k[low];
  30.         k[low]=k[high];
  31.         k[high]=temp;
  32. }
  33. int Partition(int k[],int low,int high)
  34. {
  35.         int point;

  37.         int m=low+(high-low)/2;  //优化处1
  38.         if(k[low]>k[high])
  39.         {
  40.                 swap(k,low,high);
  41.         }
  42.         if(k[m]>k[high])
  43.         {
  44.                 swap(k,m,high);
  45.         }
  46.         if(k[m]>k[low])
  47.         {
  48.                 swap(k,low,m);
  49.         }

  51.         point=k[low];
  52.         while(low<high)
  53.         {
  54.                 while(low<high&&k[high]>=point)
  55.                 {
  56.                         high--;
  57.                 }
  58.                 k[low]=k[high];   //优化处2

  60.                 while(low<high&&k[low]<=point)
  61.                 {
  62.                         low++;
  63.                 }
  64.                 k[high]=k[low];
  65.         }
  66.         k[low]=point;

  68.         return low;
  69. }
  70. void Quick(int k[],int low,int high)
  71. {
  72.         int point;
  73.         if((high-low)>MAX_LENGTH_SIZE)  //优化处3
  74.         {
  75.                 while(low<high)
  76.                 {
  77.                         point=Partition(k,low,high);
  78.                         if(point-low<high-point)   // 优化4
  79.                         {
  80.                                 Quick(k,low,point-1);
  81.                                 low=point+1;
  82.                         }
  83.                         else
  84.                         {
  85.                                 Quick(k,point+1,high);
  86.                                 high=point-1;
  87.                         }
  88.                 }
  89.         }
  90.         else
  91.         {
  92.                 InsertSort(k,low,high);
  93.         }
  94. }
  95. void QuickSort(int k[],int n)
  96. {
  97.         Quick(k,0,n-1);
  98. }
  99. int main()
  100. {
  101.         int a[10]={5,2,6,0,3,9,1,7,4,8};
  102.         QuickSort(a,10);
  103.         for(int i=0;i<10;i++)
  104.         {
  105.                 printf("%-2d ",a[i]);
  106.         }
  107.         printf("\n\n");
  108.         return 0;
  109. }
复制代码

一共是4出优化操作 代码里已分别标出优化位置
作者: 菊花爆满山    时间: 2015-6-1 12:48
最后总结一下关于各排序算法的时间复杂度问题
排序算法 平均情况 最好情况 最坏情况
冒泡排序 O(n^2) O(n) O(n^2)
选择排序 O(n^2) O(n^2) O(n^2)
直接插入排序 O(n^2)  O(n)  O(n^2)
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2)
堆排序 O(nlogn) O(nlogn) O(nlogn)
归并排序 O(nlogn) O(nlogn) O(nlogn)
快速排序 O(nlogn) O(nlogn) O(n^2)









欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2