复习排序算法

NIJUNPEI

太长时间不用，以至于连概念都忘记。既然今天例会上没写出来，那就重新复习一下所有的排序。

Day 1

时间复杂度为O(n*2)的排序算法

冒泡排序
选择排序
插入排序

冒泡排序

以由小到大排序为例，从第一个数开始两两相比较，较大的向后移动，每一次比较移动后，在后面的都是较大的数，所以每一轮冒泡以后，最后一个数字都是未排序列中最大的。

void bubbleSort(int arr[],int len)
{
   int i,j,temp;
   int flag;
   for(j = 0; j < len-1; j++){
      flag = 0;
      for(i = 0; i < len-j; i++){
         if(arr[i]<arr[i-1]){
            temp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = temp;
            flag = 1;
         }
      }

      if(flag == 0) break;
   }
}

选择排序

以由小到大排序为例，每一轮选择过程选择出最小的一个数字放到当前排序序列的最前端。

void selectSort(int arr[],int len)
{
   int i,j,temp,minIndex;
   for( i = 0; i < len-1; i++){
      minIndex = i;
      for(j = i+1; j < len; j++){
         if(arr[j]<arr[minIndex]){
            minIndex = j;
         }
      }
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
   }
}

插入排序

以由小到大排序为例，假定前n-1项是有序数列，把第n项按照应有的顺序放到序列中。

void insertSort(int arr[], int len)
{
   int i,j,temp;
   for( i = 0; i < len - 1; i++ ){
      for( j = i+1; j > 0; j-- ){
         if(arr[j]<arr[j-1]){
            temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
         }else break;
      }
   }

}

Day 1 小结

虽然三种排序算法的时间复杂度都是O(n*2),但是实际使用中随着数据量的提升，冒泡排序的效率比选择排序要差好多，以我目前的理解是冒泡排序种的交换次数要明显多于选择排序

Day 2

今天忙着复习没有搞太多，只是复习了一下希尔排序然后实现了一下，从测试代码结果上看，希尔排序的确要比时间复杂度为O(n*2)的几个算法要很多

希尔排序

希尔排序依据我现有的理解是利用了相对有顺序的序列进行插入排序时会有更少的交换次数，所以对序列进行划分先让序列大体上有序，然后再细分，最后进行一次插入排序

void shellSort(int arr[], int len)
{
   int i,j,k,temp;
   int increaseNum;
   increaseNum = len;
   while(1){
      increaseNum = increaseNum / 2;
      for(i = 0; i < increaseNum; i++){
         for(j = i+increaseNum; j < len; j += increaseNum){
            for(k = j; k > i; k -= increaseNum){
               if(arr[k] < arr[k-increaseNum]){
                  temp = arr[k];
                  arr[k] = arr[k-increaseNum];
                  arr[k-increaseNum] = temp;
               }else break;
            }
         }
      }
      if(increaseNum == 1) break;
   }
}

Day 2 小结

测试用的200个随机数排序结果显示希尔排序耗时0.035ms，冒泡排序0.236ms，选择排序0.102ms，插入排序0.089ms，希尔排序明显更高效一些。

源代码

gcc sort.c
./a.out

#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
void bubbleSort(int arr[], int len);
void selectSort(int arr[], int len);
void insertSort(int arr[], int len);
void shellSort(int arr[], int len);
int main()
{
   int i;
   int arr[2000];
   int selectMethod;
   struct timeval start,end;//执行时间计时
   int interval;//us微秒为单位的时间差
   //生成随机数数列
   srand((unsigned)time(0));
   for(i = 0; i < 2000; i++){
      arr[i] = rand()%1000;
      printf("生成第%d个数字为%d\n",i,arr[i]);
   }
   //选择排序算法
   printf("Choose sort func:\n1.bubble\n2.select\n3.insert\n4.shell\n");
   scanf("%d",&selectMethod);
   gettimeofday(&start, NULL);//计时开始
   switch(selectMethod){
      case 1: 
         bubbleSort(arr, 200);
      case 2:
         selectSort(arr, 200);
      case 3:
         insertSort(arr, 200);
      case 4:
         shellSort(arr, 200);
   }
   gettimeofday(&end, NULL);//计时结束
   interval = 1000000*(end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec);
   //打印排序结果
   printf("排序后数字序列:\n");
   for(i = 0; i < 200; i++){
      printf("%d\n",arr[i]);
   }
   printf("花费时间: %f ms\n",interval/1000.0);
}
void bubbleSort(int arr[],int len)
{
   int i,j,temp;
   int flag;
   for(j = 0; j < len-1; j++){
      flag = 0;
      for(i = 0; i < len-j; i++){
         if(arr[i]<arr[i-1]){
            temp = arr[i];
            arr[i] = arr[i-1];
	    arr[i-1] = temp;
	    flag = 1;
         }
      }

      if(flag == 0) break;
   }
}
void selectSort(int arr[],int len)
{
   int i,j,temp,minIndex;
   for( i = 0; i < len-1; i++){
      minIndex = i;
      for(j = i+1; j < len; j++){
         if(arr[j]<arr[minIndex]){
	    minIndex = j;
	 }
      }
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
   }
}
void insertSort(int arr[], int len)
{
   int i,j,temp;
   for( i = 0; i < len - 1; i++ ){
      for( j = i+1; j > 0; j-- ){
         if(arr[j]<arr[j-1]){
	    temp = arr[j];
	    arr[j] = arr[j-1];
	    arr[j-1] = temp;
	 }else break;
      }
   }

}
void shellSort(int arr[], int len)
{
   int i,j,k,temp;
   int increaseNum;
   increaseNum = len;
   while(1){
      increaseNum = increaseNum / 2;
      for(i = 0; i < increaseNum; i++){
         for(j = i+increaseNum; j < len; j += increaseNum){
            for(k = j; k > i; k -= increaseNum){
               if(arr[k] < arr[k-increaseNum]){
                  temp = arr[k];
                  arr[k] = arr[k-increaseNum];
                  arr[k-increaseNum] = temp;
               }else break;
            }
         }
      }
      if(increaseNum == 1) break;
   }
}

wqy

昨天的冒泡排序怎么不敢上来挑战一下

NIJUNPEI

@wqy 人多了紧张0.0

oasis

计数排序是之前打比赛有时候会用到的一种排序，也分享一下。

计数排序是一种非基于比较的稳定的排序算法。在一定条件下，运行时间为O(n)。

基本思想：对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定），之后将x直接存放在最终的位置上

条件：

1、n个输入元素中的每一个都是在0到k区间内的一个整数；
2、k=O(n)。

伪代码：

COUNTING-SORT(A,B,k) //输入数组为A[1...n], 输出数组为B[1...n], C[0...k]提供临时存储空间

1 for i=0 to k

2 C[i]=0

3 for j=1 to A.length //最后得到 C[i]记录的是A[1...n]中等于i的元素的个数

4 C[A[j]]=C[A[j]]+1

5 for i=1 to k //最后得到 C[i]记录的是A[1..n]中小于或等于i的元素的个数

6 C[i]=C[i]+C[i-1]

7 for j=A.length downto 1

8 B[C[A[j]]]=A[j]

9 C[A[j]]=C[A[j]]-1

LiangFS

请问空间复杂度为多少

jaychou

不知道各位有没有听过睡觉排序算法（233333...