十种常见排序算法欢聚一堂

十种常见排序算法欢聚一堂1.常见排序算法分类十种常见排序算法一般分为以下几种:(1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆排序)、归并排序(二路归并排序和多路归并排序);(2)线性时间非比较类排序:计数排序、基数排序和桶排序。总结:(1)在比较类排序中,归并排序最快,其次是快速排序和堆排序,两者不相伯仲,但是有一点需要………………

在这里插入图片描述

1.常见排序算法分类

常见排序算法一般分为以下两大类:

  • 非线性时间比较类排序
    交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆排序)、归并排序(二路归并排序和多路归并排序);
  • 线性时间非比较类排序
    计数排序、基数排序和桶排序。

在比较类排序中,归并排序最快,其次是快速排序和堆排序,两者不相伯仲,但是有一点需要注意,数据初始排序状态对堆排序不会产生太大的影响,而快速排序却恰恰相反。

线性时间非比较类排序一般要优于非线性时间比较类排序,但前者对待排序元素的要求较为严格,比如计数排序要求待排序数的最大值不能太大,桶排序要求元素按照hash分桶后桶内元素的数量要均匀。线性时间非比较类排序的典型特点是以空间换时间。

注意: 本文所有示例代码均为递增排序。

2.非线性时间比较类排序

2.1 交换类排序

交换排序的基本方法是:两两比较待排序记录的排序码,交换不满足顺序要求的偶对,直到全部满足位置。常见的冒泡排序和快速排序就属于交换类排序。

2.1.1 冒泡排序

算法思想:
从数组中第一个数开始,依次遍历数组中的每一个数,通过相邻比较交换,每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

算法步骤:
(1)从数组中第一个数开始,依次与下一个数比较并次交换比自己小的数,直到最后一个数。如果发生交换,则继续下面的步骤,如果未发生交换,则数组有序,排序结束,此时时间复杂度为O(n);
(2)每一轮”冒泡”结束后,最大的数将出现在乱序数列的最后一位。重复步骤(1)。

**稳定性:**稳定排序。

时间复杂度: O ( n ) O(n) O(n) ~ O ( n 2 ) O(n^2) O(n2),平均 O ( n 2 ) O(n^2) O(n2)

最好的情况:如果待排序数据序列为正序,则一趟冒泡就可完成排序,排序码的比较次数为 n-1 次,且没有移动,时间复杂度为O(n)。

最坏的情况:如果待排序数据序列为逆序,则冒泡排序需要 n-1 次趟起泡,每趟进行n-i次排序码的比较和移动,即比较和移动次数均达到最大值:
比较次数: C m a x = ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) / 2 = O ( n 2 ) C_{max}=\sum\limits_{i=1}^{n-1}(n-i)=n(n-1)/2=O(n^2) Cmax=i=1n1(ni)=n(n1)/2=O(n2)
移动次数等于比较次数,因此最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)

示例如下:

void bubbleSort(int array[], int len) { 
   
	// 循环的次数为数组长度减一,剩下的一个数不需要排序
	for(int i=0; i<len-1; ++i)  { 
   
		bool noswap=true;
		// 循环次数为待排序数第一位数冒泡至最高位的比较次数
		for(int j=0;j<len-i-1;++j) { 
   
			if(array[j]>array[j+1]) { 
   
				array[j]=array[j]+array[j+1];
				array[j+1]=array[j]-array[j+1];
				array[j]=array[j]-array[j+1];
				// 交换或者使用如下方式
				//a=a^b;
				//b=b^a;
				//a=a^b;
				noswap=false;
			}
		}
		if(noswap) break;
	}
}

2.1.2 快速排序

快速排序由 C. A. R. Hoare在 1962 年提出,是对冒泡排序的一种改进,采用了一种分治的思想,是对冒泡排序的改进,故又称分区交换排序。

在这里插入图片描述

算法原理:
(1)从待排序的 n 个记录中任意选取一个记录(通常选取第一个记录)为分界值;
(2)把所有小于分界值的记录移动到左边,把所有大于分界值的记录移动到右边,中间位置填分界值,称之为第一趟排序;
(3)然后对前后两个子序列分别重复上述过程,直到所有记录都排好序。

稳定性: 不稳定排序。

时间复杂度: O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) ~ O ( n 2 ) O(n^2) O(n2),平均 O ( n l g n ) O(nlgn) O(nlgn)

最好的情况:是每趟排序结束后,每次划分使两个子文件的长度大致相等,时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

最坏的情况:是待排序记录已经排好序,第一趟经过n-1次比较后第一个记录保持位置不变,并得到一个n-1个元素的子记录;第二趟经过n-2次比较,将第二个记录定位在原来的位置上,并得到一个包括n-2个记录的子文件,依次类推,这样总的比较次数是:
C m a x = ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) / 2 = O ( n 2 ) C_{max}=\sum\limits_{i=1}^{n-1}(n-i)=n(n-1)/2=O(n^2) Cmax=i=1n1(ni)=n(n1)/2=O(n2)

空间复杂度: O(1)。

2.1.2.1 递归版

快排有很多种实现方式,比如交换法、填充法和双指针前移法。因为其属于交换类排序,所以这里建议采用交换法来实现。其他实现方式可参考快速排序的三种实现方式以及非递归版本

交换法:

// quicksort 交换法实现快排。
// a:待排序数组 low:最低位的下标 high:最高位的下标。
void quicksort(int arr[],int low, int high) { 
   
	if(low>=high) { 
   
		return;
  	}

	int left=low;        // 左下标
	int right=high;      // 右下标
	int key=arr[low];    // 用数组的第一个记录作为分界值

	// 第一轮,找到分界值对应的下标。
	while (left != right) { 
   
		// 从右向左遍历,找小于分界值的记录。
		while(right > left && arr[right]>=key)
      		right--;
		// 从从向右遍历,找大于分界值的记录。
		while(left < right && arr[left]<=key)
      		left++;
    	// 交换。 
    	int tmp = arr[right];
		arr[right] = arr[left];
    	arr[left] = tmp;
	}
  	// 分界值与对应位置的值交换。
  	int tmp = arr[left];
 	arr[left] = arr[low];
  	arr[low] = tmp;
  
	quicksort(arr,low,left-1);	// 递归处理左分区
	quicksort(arr,left+1,high);	// 递归处理右分区
}

下面用 Go 实现。

// quicksort 快速排序。
func quicksort(values []int, left int, right int) { 
   
	if left >= right { 
   
		return
	}
	i := left
	j := right
	key := values[left]

	// 第一轮,找到分界值对应的下标。
	for i != j { 
   
		// 从右往左遍历,找到第一个小于分界值的值。
		for j > i && values[j] >= key { 
   
			j--
		}
		// 从左往右遍历,找到第一个大于分界值的值。
		for i < j && values[i] <= key { 
   
			i++
		}
		// 交换
		values[i], values[j] = values[j], values[i]
	}
	// 分界值与指定位置的数交换。
	values[i], values[left] = values[left], values[i]

	quicksort(values, left, i-1)  // 递归处理左分区。
	quicksort(values, i+1, right) // 递归处理右分区。
}

填充法:

// quicksort 填充法实现快排。
// a:待排序数组 low:最低位的下标 high:最高位的下标。
void quicksort(int a[],int low, int high) { 
   
	if(low>=high) return;

	int left=low;
	int right=high;
	int key=a[left];    // 用数组的第一个记录作为分界值

	// 第一趟排序
	while(left != right) { 
   
		// 从右向左扫描,找第一个值小于 key 的记录,并放到 key 的位置
		while(left<right && a[right]>=key)
			right--;
		a[left]=a[right];

		// 从左向右扫描,找第一个码值大于 key 的记录,并交换到右边下标为 right 的位置
		while(left<right && a[left]<=key)
			left++;
		a[right]=a[left];
	}
	a[left]=key;    			// 分区元素放到正确位置
	
	quicksort(a, low, left-1);	// 重复对左边分区的处理
	quicksort(a, left+1, high);	// 重复对右边分区的处理
}

2.1.2.2 非递归版

有时候面试时,面试官可能需要我们写出非递归版本的快排,因为待排序数值很多时,递归深度太深,可能会导致栈溢出。

那如何实现非递归版本的快排呢?

递归改非递归一般需要借助栈,因为栈后进先出的特性,刚好符合函数递归调用的过程。

我们可以使用栈保存下次要处理的起始与结束下标。

// quicksortNonRecursive 非递归实现快排。
func quicksortNonRecursive(values []int) { 
   
	if len(values) <= 1 { 
   
		return
	}
	stack := list.New()
	stack.PushBack(len(values) - 1)
	stack.PushBack(0)

	for stack.Len() > 0 { 
   
		// 出栈。
		left := stack.Remove(stack.Back()).(int)
		right := stack.Remove(stack.Back()).(int)
		key := values[left]
		i, j := left, right
		fmt.Println("start:", i, j)
		for i != j { 
   
			// 从右往左遍历,找到第一个小于分界值的值。
			for j > i && values[j] >= key { 
   
				j--
			}
			// 从左往右遍历,找到第一个大于分界值的值。
			for i < j && values[i] <= key { 
   
				i++
			}
			// 交换
			values[i], values[j] = values[j], values[i]
		}
		// 交换
		values[i], values[left] = values[left], values[i]
		
		// 右侧起始下标入栈。
		if i+1 < right { 
   
			stack.PushBack(right)
			stack.PushBack(i + 1)
		}

		// 左侧起始下标入栈。
		if i-1 > left { 
   
			stack.PushBack(i - 1)
			stack.PushBack(left)
		}
	}
}

2.2 插入类排序

插入排序的基本方法是:每步将一个待排序的记录,按其排序码大小,插到前面已经排序的文件中的适当位置,直到全部插入完为止。

2.2.1 直接插入排序

原理: 从待排序的n个记录中的第二个记录开始,依次与前面的记录比较并寻找插入的位置,每次外循环结束后,将当前的数插入到合适的位置。

稳定性: 稳定排序。

时间复杂度: O ( n ) O(n) O(n) ~ O ( n 2 ) O(n^2) O(n2),平均 O ( n 2 ) O(n^2) O(n2)

空间复杂度: O(1)。

最好情况:当待排序记录已经有序,这时需要比较的次数是 C m i n = n − 1 = O ( n ) C_{min}=n-1=O(n) Cmin=n1=O(n)

最坏情况:如果待排序记录为逆序,则最多的比较次数为 C m a x = ∑ i = 1 n − 1 ( i ) = n ( n − 1 ) 2 = O ( n 2 ) C_{max}=\sum\limits_{i=1}^{n-1}(i)=\frac{n(n-1)}2=O(n^2) Cmax=i=1n1(i)=2n(n1)=O(n2)

示例代码:

//@brief: 快速排序
//@param: A:输入数组 len:数组长度
void insertSort(int A[], int len) { 
   
	int tmp;
	for ( int i=1; i<len; i++ )
	{ 
   
	  int j=i-1;
      tmp=A[i]; 
	  //查找到要插入的位置
	  while( j >= 0 && A[j] > tmp)
	  { 
   
          A[j+1]=A[j];
		  j--;
	  }
	  A[j+1]=tmp;	//插入到正确位置
	}
}

2.2.2 Shell 排序

Shell 排序又称缩小增量排序, 由D. L. Shell在1959年提出,是对直接插入排序的改进。

原理: Shell排序法是对相邻指定距离(称为增量)的元素进行比较,并不断把增量缩小至1,完成排序。

Shell排序开始时增量较大,分组较多,每组的记录数目较少,故在各组内采用直接插入排序较快,后来增量 d i d_i di逐渐缩小,分组数减少,各组的记录数增多,但由于已经按 d i − 1 d_{i-1} di1分组排序,文件叫接近于有序状态,所以新的一趟排序过程较快。因此Shell排序在效率上比直接插入排序有较大的改进。

在直接插入排序的基础上,将直接插入排序中的1全部改变成增量d即可,因为Shell排序最后一轮的增量d就为1。

稳定性: 不稳定排序。

时间复杂度: O ( n 1.3 ) O(n^{1.3}) O(n1.3) O ( n 2 ) O(n^2) O(n2)。Shell排序算法的时间复杂度分析比较复杂,实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明,若增量的取值比较合理,Shell排序算法的时间复杂度约为 O ( n 1.3 ) O(n^{1.3}) O(n1.3)

对于增量的选择,Shell 最初建议增量选择为n/2,并且对增量取半直到 1;D. Knuth教授建议 d i + 1 = ⌊ d i − 1 3 ⌋ d_{i+1}=\lfloor\frac{d_i-1}3\rfloor di+1=3di1序列。

//@brief: Shell排序
//@param: A:输入数组,len:数组长度,d:初始增量(分组数)
void shellSort(int A[],int len, int d) { 
   
	//循环的次数为增量缩小至1的次数
	for(int inc=d;inc>0;inc/=2)
	{ 
   
		for(int i=inc;i<len;++i)
		{ 
          
			//循环的次数为第一个分组的第二个元素到数组的结束
			int j=i-inc;
			int temp=A[i];
			while(j>=0&&A[j]>temp)
			{ 
   
				A[j+inc]=A[j];
				j=j-inc;
			}

			//防止自我插入
			if((j+inc)!=i)
			{ 
   
				A[j+inc]=temp;//插入记录
			}
		}
	}
}

注意: 从代码中可以看出,增量每次变化取前一次增量的一般,当增量d等于1时,shell排序就退化成了直接插入排序了。

2.3 选择类排序

选择类排序的基本方法是:每步从待排序记录中选出排序码最小的记录,顺序放在已排序的记录序列的后面,知道全部排完。

2.3.1 简单选择排序(又称直接选择排序)

原理: 从所有记录中选出最小的一个数据元素与第一个位置的记录交换;然后在剩下的记录当中再找最小的与第二个位置的记录交换,循环到只剩下最后一个数据元素为止。

稳定性: 不稳定排序。

时间复杂度: 最坏、最好和平均复杂度均为 O ( n 2 ) O(n^2) O(n2),因此,简单选择排序也是常见排序算法中性能最差的排序算法。简单选择排序的比较次数与文件的初始状态没有关系,在第i趟排序中选出最小排序码的记录,需要做n-i次比较,因此总的比较次数是: ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) / 2 = O ( n 2 ) \sum\limits_{i=1}^{n-1}(n-i)=n(n-1)/2=O(n^2) i=1n1(ni)=n(n1)/2=O(n2)

示例代码:

void selectSort(int A[],int len) { 
   
	int i,j,k;
	for(i=0;i<len;i++){ 
   
       k=i;
	   for(j=i+1;j<len;j++){ 
   
		   if(A[j]<A[k])
			   k=j;
	   }
	   if(i!=k){ 
   
           A[i]=A[i]+A[k];
           A[k]=A[i]-A[k];
		   A[i]=A[i]-A[k];
	   }
	}
}

2.3.2 堆排序

直接选择排序中,第一次选择经过了n-1次比较,只是从排序码序列中选出了一个最小的排序码,而没有保存其他中间比较结果。所以后一趟排序时又要重复许多比较操作,降低了效率。J. Willioms 和 Floyd 在1964年提出了堆排序方法,避免这一缺点。

2.3.2.1 堆的性质

(1)性质:堆是一棵完全二叉树,但完全二叉树不一定是堆。
(2)分类:大顶堆:父节点不小于子节点键值,小顶堆:父节点不大于子节点键值;图展示一个小顶堆:
这里写图片描述
(3)左右孩子:没有大小的顺序。
(4)堆的存储:一般都用数组来存储堆,i 结点的父结点下标为 ( i – 1 ) / 2 (i–1)/2 (i–1)/2。它的左右子结点下标分别为 2 ∗ i + 1 2 * i + 1 2i+1 2 ∗ i + 2 2 * i + 2 2i+2。如第 0 个结点左右子结点下标分别为 1 和 2。
这里写图片描述

2.3.2.2 堆的基本操作

(1)建立。

以最小堆为例,如果以数组存储元素时,一个数组具有对应的树表示形式,但树并不满足堆的条件,需要重新排列元素,可以建立“堆化”的树。

这里写图片描述

(2)插入。

将一个新元素插入到表尾,即数组末尾时,如果新构成的二叉树不满足堆的性质,需要重新排列元素,下图演示了插入15时,堆的调整。

这里写图片描述

(3)删除。

堆排序中,删除一个元素总是发生在堆顶,因为堆顶的元素是最小的(小顶堆中)。表中最后一个元素用来填补空缺位置,结果树被更新以满足堆条件。

这里写图片描述

2.3.2.3 堆操作实现

(1)插入(push)需上浮。

每次插入都是将新数据放在数组最后。

新数据的父结点到根结点必然为一个有序数列,现在的任务是将这个新数据插入到这个有序数据中。这就类似于直接插入排序中将一个数据插入到有序区间中,这是结点“上浮”调整。

// 新加入 i 结点,其父结点为(i-1)/2。
// 参数:a:数组,i:新插入元素在数组中的下标。
void minHeapFixUp(int a[], int i) { 
   
    int j, temp;  
    temp = a[i];  
    j = (i-1)/2;      // 父结点 
    while (j >= 0 && i != 0) { 
     
        if (a[j] <= temp) // 如果父节点不大于新插入的元素,停止寻找
            break;  
        a[i]=a[j];     // 把较大的子结点往下移动,替换它的子结点
        i = j;  
        j = (i-1)/2;  
    }  
    a[i] = temp;  
}

因此,插入数据到最小堆时:

// 在最小堆中加入新的数据data 
// a:数组,index:插入的下标,
void minHeapAddNumber(int a[], int index, int data) { 
   
    a[index] = data;  
    minHeapFixUp(a, index);  
} 

(2)删除(pop)需下沉。

删除一般指的是删除堆顶元素,在堆顶元素被拿掉后,将末尾元素置换上来,然后进行下沉操作

下沉步骤:

  1. 调整时先在左右子结点中找最小的,如果父结点不大于这个最小的子结点说明不需要调整了。
  2. 反之将最小的子结点换到父结点的位置。此时父结点实际上并不需要换到最小子结点的位置,因为这可能不是父结点的最终位置。
  3. 重复步骤 2,直到子节点不小于父节点。
// a 为数组,从 index 结点开始调整, len 为结点总数。
// 从 0 开始计算,index 结点的子结点为 2*index+1 和 2*index+2。len/2-1 为最后一个非叶子节点。
void minHeapFixDown(int a[], int len, int index) { 
   
	if(index>(len/2-1)) // index 为叶子结点不用调整
		return;
	int tmp=a[index];
	lastIndex=index;
	while(index<=len/2-1) { 
         // 当下沉到叶子节点时,就不用调整了
		if(a[2*index+1]<tmp) { 
      // 如果左子节点小于待调整节点
			lastIndex = 2*index+1;
		}
		// 如果存在右子节点且小于左子节点和待调整节点
		if(2*index+2<len && a[2*index+2]<a[2*index+1] && a[2*index+2]<tmp) { 
   
			lastIndex=2*index+2;
		}
		// 如果左右子节点有一个小于待调整节点,选择最小子节点进行上浮
		if(lastIndex!=index) { 
     
			a[index]=a[lastIndex];
			index=lastIndex;
		}
		else break;             //否则待调整节点不用下沉调整
	}
	a[lastIndex]=tmp;           //将待调整节点放到最后的位置
}

根据算法思想,建议大家自行给出实现,切勿看示例代码去理解算法,而是理解算法思想给出自己的实现,否则很快就会忘记。

(3)建堆。

有了堆的插入和删除后,再考虑下如何对一个数组进行堆化。要一个一个的从数组中取出数据来建立堆吧,不用!先看一个数组,如下图:

这里写图片描述

很明显,对叶子结点来说,可以认为它已经是一个合法的堆了,即 20,60, 65, 4, 49 都分别是一个合法的堆。只要从 A[4]=50 开始向下调整就可以了。然后再取 A[3]=30,A[2]=17,A[1]=12,A[0]=9 分别做一次向下调整操作就可以了。

下图展示了这些步骤:

这里写图片描述

写出堆化数组的代码:

// 建立最小堆。
// a:数组,n:数组长度
void buildMinHeap(int a[], int n) { 
   
    for (int i = n/2-1; i >= 0; i--) { 
   
		minHeapFixDown(a, i, n);
    }
}  

2.3.2.4 堆排序的实现

由于堆也是用数组来存储的,故对数组进行堆化后,第一次将A[0]与A[n – 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n – 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。有点类似于直接选择排序。

因此,完成堆排序并没有用到前面说明的插入操作,只用到了建堆和节点向下调整的操作,堆排序的操作如下:

//@param: array:待排序数组 len:数组长度
void heapSort(int array[],int len) { 
   
	// 建堆
	buildMinHeap(array,len); 
	
	// 最后一个叶子节点和根节点交换,并进行堆调整,交换次数为len-1次
	for(int i=len-1; i>0; i--) { 
   
		// 最后一个叶子节点交换。
		array[i]=array[i]+array[0];
		array[0]=array[i]-array[0];
		array[i]=array[i]-array[0];
        
        // 堆调整
		minHeapFixDown(array, i, 0);  
	}
}  

(1)稳定性:不稳定排序。

(2)时间复杂度。
由于每次重新恢复堆的时间复杂度为 O(logN),共 N – 1 次堆调整操作,再加上前面建立堆时 N/2 次向下调整,每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为 O(N * logN)。

最坏情况:如果待排序数组是有序的,仍然需要 O(N * logN) 复杂度的比较操作,只是少了移动的操作;

最好情况:如果待排序数组是逆序的,不仅需要O(N * logN)复杂度的比较操作,而且需要O(N * logN)复杂度的交换操作。总的时间复杂度还是O(N * logN)。

因此,堆排序和快速排序在效率上是差不多的,但是堆排序一般优于快速排序的重要一点是,数据的初始分布情况对堆排序的效率没有大的影响。

下面给出 Golang 版本的完成实现堆排序。

// minHeapFixDown 下沉指定结点。
// 注意:从 0 开始计算,index 结点的子结点为 2*index+1 和 2*index+2。l 为结点数,那么 l/2-1 为最后一个非叶子节点。
func minHeapFixDown(vs []int, l, index int) { 
   
	// 叶子结点不用下沉。
	if index > (l/2 - 1) { 
   
		return
	}

	tmp := vs[index]
	lastIndex := index

	// 当下沉到叶子结点时,就不用调整了。
	for index <= l/2-1 { 
   
		if vs[2*index+1] < tmp { 
    // 如果左子节点小于待调整结点
			lastIndex = 2*index + 1
		}
		// 如果存在右子节点且小于左子节点和待调整节点。
		if 2*index+2 < l && vs[2*index+2] < vs[2*index+1] && vs[2*index+2] < tmp { 
   
			lastIndex = 2*index + 2
		}
		// 无需调整。
		if lastIndex == index { 
   
			break
		}
		// 最小子节点进行上浮。
		vs[index] = vs[lastIndex]
		// 对最小子节点重复之前的操作。
		index = lastIndex
	}
	// 将待调整节点放到最后的位置。
	vs[lastIndex] = tmp
}

// buildHeap 建堆。
func buildHeap(vs []int) { 
   
	l := len(vs)
	for i := l/2 - 1; i >= 0; i-- { 
   
		minHeapFixDown(vs, l, i)
	}
}

// heapsort 小顶堆实现降序排序。
func heapsort(vs []int) { 
   
	// 先堆化数组。
	buildHeap(vs)

	// 循环删除堆顶元素,与数组末尾元素交换。
	for i := len(vs) - 1; i > 0; i-- { 
   
		vs[0], vs[i] = vs[i], vs[0]
		// 下沉堆顶元素。
		minHeapFixDown(vs, i, 0)
	}
}

正确性验证:

func main() { 
   
	values := []int{ 
   1, 2, 3, 4, 5, 66, 7, 88, 9, 0}
	heapsort(values)
	fmt.Println(values)
}

运行输出:

[88 66 9 7 5 4 3 2 1 0]

2.4 归并排序

算法思想: 归并排序属于比较类非线性时间排序,比较类排序中性能佳,应用较为广泛。 归并排序是分治法(Divide and Conquer)的一个典型应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。一般情况,归并排序指二路归并排序。

稳定性: 稳定排序算法。

时间复杂度: 最坏、最好和平均时间复杂度都是 O(nlgn)。

具体的实现参见另一篇blog:二路归并排序简介及其并行化

3.线性时间非比较类排序

3.1 计数排序

计数排序是一个非比较类排序算法,该算法于 1954 年由 Harold H. Seward 提出,它的优势在于在对于较小范围内的整数排序。

时间复杂度为 Ο(n+k)(其中 k 是待排序数的最大值),快于任何比较类排序算法,缺点就是非常消耗空间。很明显,如果而且当O(k)>O(n*log(n)) 的时候其效率反而不如比较类排序,比如快速排序、堆排序和归并排序。

算法原理:
基本思想是对于给定的输入序列中的每一个元素 x,确定该序列中值小于 x 的元素的个数。一旦有了这个信息,就可以将 x 直接存放到最终的输出序列的正确位置上。例如,如果输入序列中只有 17 个元素的值小于 x 的值,则 x 可以直接存放在输出序列的第 18 个位置上。当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,往前找到空位插入即可。

算法步骤:
(1)找出待排序的数组中最大的元素 k,申请一个长度为 k + 1 的中间数组 C。
(2)遍历待排序数列,统计每个值为 i 的元素出现的次数,存入数组 C 的第 i 项。
(3)对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加)。
(4)反向填充目标数组:将每个元素i放在新数组的第 C(i) 项,每放一个元素就将 C(i) 减去 1。

时间复杂度: Ο(n+k)。

空间复杂度: Ο(k)。

要求: 待排序数中最大数值不能太大。

稳定性: 稳定。

示例如下:

#define MAXNUM 20 //待排序数的最大个数
#define MAX 100 //待排序数的最大值
int sorted_arr[MAXNUM]={ 
   0};

// 计数排序。
// arr 待排序数组,n 待排序数组长度,sorted_arr 排好序的数组。
void countSort(int *arr, int n, int *sorted_arr) { 
   
	int i;   
    int *count_arr = (int *)malloc(sizeof(int) * (MAX+1));  
  
    // 初始化计数数组 
	memset(count_arr, 0, sizeof(int) * (MAX+1));

    // 第一步:统计 i 的次数。
    for(i = 0; i<n; i++) { 
   
        count_arr[arr[i]]++;
    }
    
    // 第二步:对所有的计数累加,作用是统计 arr 数组值和小于 arr 数组值出现的个数。
    for(i = 1; i<=MAX; i++) { 
   
        count_arr[i] += count_arr[i-1];
    }
    
    // 第三步:逆向遍历源数组(保证稳定性),根据计数数组中对应的值填充到新的数组中。
    for(i = n-1; i>=0; i--) { 
   
		// count_arr[arr[i]] 表示 arr 数组中包括 arr[i] 和小于 arr[i] 的总数。
        sorted_arr[count_arr[arr[i]]-1] = arr[i];

		// 如果 arr 数组中有相同的数,arr[i] 的下标减一。
        count_arr[arr[i]]--;    
    }
	free(count_arr);
}

注意: 计数排序是典型的以空间换时间的排序算法,对待排序的数据有严格的要求,比如待排序的数值中包含负数,最大值都有限制,请谨慎使用。

3.2 基数排序

基数排序属于“分配式排序”(distribution sort),是非比较类线性时间排序的一种,又称“桶子法”(bucket sort)。顾名思义,它是透过键值的部分信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。

具体描述即代码示例见本人另一篇blog:基数排序简介及其并行化

3.3 桶排序

桶排序也是分配排序的一种,但其是基于比较排序的,这也是与基数排序最大的区别所在。

**思想:**桶排序算法想法类似于散列表。首先要假设待排序的元素输入符合某种均匀分布,例如数据均匀分布在[ 0,1)区间上,则可将此区间划分为10个小区间,称为桶,对散布到同一个桶中的元素再排序。

**要求:**待排序数长度一致。

排序过程:
(1)设置一个定量的数组当作空桶子;
(2)寻访序列,并且把记录一个一个放到对应的桶子去;
(3)对每个不是空的桶子进行排序。
(4)从不是空的桶子里把项目再放回原来的序列中。

例如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序。

时间复杂度:
对N个关键字进行桶排序的时间复杂度分为两个部分:
(1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。

(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序,对于N个待排数据,M个桶,平均每个桶[N/M]个数据,则桶内排序的时间复杂度为 ∑ i = 1 M O ( N i ∗ l o g N i ) = O ( N ∗ l o g N M ) \sum\limits_{i=1}^MO(N_i*logN_i)=O(N*log\frac{N}{M}) i=1MO(NilogNi)=O(NlogMN) 。其中 N i N_i Ni 为第i个桶的数据量。

因此,平均时间复杂度为线性的 O(N+C),C为桶内排序所花费的时间。当每个桶只有一个数,则最好的时间复杂度为:O(N)。

示例代码:

typedef struct node { 
    
	 int keyNum;//桶中数的数量
	 int key;   //存储的元素
	 struct node * next;  
 }KeyNode;

 //keys待排序数组,size数组长度,bucket_size桶的数量
 void inc_sort(int keys[],int size,int bucket_size) { 
    
	 KeyNode* k=(KeyNode *)malloc(sizeof(KeyNode)); //用于控制打印
	 int i,j,b;
	 KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); 
     for(i=0;i<bucket_size;i++)
	 { 
     
		 bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); 
		 bucket_table[i]->keyNum=0;//记录当前桶中是否有数据
	     bucket_table[i]->key=0;   //记录当前桶中的数据 
		 bucket_table[i]->next=NULL; 
	 }    

	 for(j=0;j<size;j++) { 
      
		 int index;
		 KeyNode *p;
		 KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));   
	     node->key=keys[j];  
		 node->next=NULL;  

		 index=keys[j]/10;        //映射函数计算桶号 
		 p=bucket_table[index];   //初始化P成为桶中数据链表的头指针 
		 if(p->keyNum==0)//该桶中还没有数据 
		 { 
       
			 bucket_table[index]->next=node;    
			 (bucket_table[index]->keyNum)++;  //桶的头结点记录桶内元素各数,此处加一
		 }
		 else//该桶中已有数据 
		 { 
      
			 //链表结构的插入排序 
			 while(p->next!=NULL&&p->next->key<=node->key)   
				 p=p->next;    
			 node->next=p->next;     
			 p->next=node;      
			 (bucket_table[index]->keyNum)++;   
		 }
	 }
	 //打印结果
	 for(b=0;b<bucket_size;b++) { 
   
		 //判断条件是跳过桶的头结点,桶的下个节点为元素节点不为空
		 for(k=bucket_table[b];k->next!=NULL;k=k->next)  
		 { 
   
			 printf("%d ",k->next->key);
		 }
	}
 }  

参考文献

[1] 计数排序、桶排序和基数排序
[2] 白话经典算法系列之六 快速排序 快速搞定
[3] 白话经典算法系列之七 堆与堆排序
[4] 张乃孝.算法与数据结构——C语言描述(第二版).高等教育出版社
[5] 百度百科.计数排序

今天的文章十种常见排序算法欢聚一堂分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/27277.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注