首页 > 代码库 > 排序算法小结

排序算法小结

2024-08-03 14:59:18   219人阅读

  我将对几种经典的排序算法进行一个小结，着重于代码的实现。

排序算法有冒泡排序、快速排序、直接插入排序、希尔排序、选择排序等。

 

排序算法1：冒泡排序

算法原理：（从后往前）
  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法分析：

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
C(min)=n-1，M(min)=0
所以，冒泡排序最好的时间复杂度为O(n)。
若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
C(max)=O(n2)
M(max)=O(n2)
 
 
冒泡排序的最坏时间复杂度为O(n2)。
综上，因此冒泡排序总的平均时间复杂度为O(n2)。

算法稳定性：不稳定性排序算法

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
 
核心代码：
 1 for(int i=0;i<N-1;i++) 2   for(int j=0;j<N-1-i;j++) 3     if( a[j]>a[j+1] ) 4    { 5       int temp=a[j]; 6       a[j]=a[a+1]; 7       a[j+1]=temp; 8    } 9 10 //或者11 12 int bool=0;   //用于判断数组是否已经有序13 for(int i=N-1;i<=1,bool==0;i++)14 {15   bool=1;     //先设定有序16   for(int j=0;j<i-1;j++)17     if( a[j]>a[j+1] )18     { 19        //...   交换a[j]和a[j+1]20        bool=0;   //标记数组无序 21     }22 }

 

排序算法2：快速排序（对冒泡排序的改进）

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

一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
 
算法稳定性：不稳定性排序算法
 
快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
 
核心代码：
 1 //执行一次快速排序 2 int quick(int s[],int start,int end) 3 { 4   int i,j; 5   i=start; 6   j=end; 7   s[0]=s[start];   //设置基准值 8  while( i<j ) 9  { 10      while( i<j && s[j]>s[0] )11           j--;         //位置左移12      if( i<j )   //当s[j]<=s[0]时13      {14          s[i]=s[j];    //将小于等于基准值的s[j]放到s[i]位置15          i++;16      }  17 18     while( i<j && s[i]<=s[0] )19        i++;        //位置右移
20     if( i<j )//当s[j]>s[0]时
21     {22        s[j]=s[i]; //将大于基准值的s[i]放到s[j]位置
23        j--;24     }25  }26   s[i]=s[0];     //将基准值放入指定位置
27   if( start<i )28      quick(s,start,j-1);//对分割的部分进行递归
29   if( end>i )30      quick(s,j+1,end);31 }

 

排序算法3：直接插入排序

算法思想：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
 
算法稳定性：稳定性排序算法
 
核心代码：
 1 for(int i=2;i<=n;i++) 2 { 3   s[0]=s[i];   //s[0]作为监视哨 4   j=i-1;        //从右向左遍历有序数组 5   while( s[0]<s[j] )   //找出s[0]要插入的位置 6   { 7         s[j+1]=s[j];     //监视哨较小，数据右移 8       j--; 9    }10   s[j+1]=s[0];        //在确定的位置插入监视哨s[0]11 }

 

排序算法4：希尔排序（直接插入排序的改进）

基本思想：先取一个小于n的整数d1作为第一个增量,，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量等于1，即所有记录放在同一组中进行直接插入排序为止。

 

算法稳定性：不稳定性排序算法

 由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

 

核心代码：

 1 while( k>0 )  // k为增量 2 { 3   for(i=k;i<n;i++) 4   { 5       j=i-k; 6       if( a[j]>a[j+k] ) 7       { 8           int temp=a[j]; 9           a[j]=a[j+1];10           a[j+1]=temp;11       }12   }13   k/=2;     //增量k减小14 }

 

排序算法5：选择排序

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

 

算法稳定性：不稳定性排序算法

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2和5的相对前后顺序就被破坏了，所以选择排序不是一个不稳定的排序算法。

 

核心代码：

 

1 for(int i=0;i<N-1;i++)2   for(int j=i+1;j<N;j++)      //找出剩余数组中的最小（最大）的数3      if( a[i]>a[j] )                 //排在有序数组的后面4      {5           int temp=a[i];6           a[i]=a[j];7           a[j]=temp;8      }

 

排序算法小结


联系
我们