文档章节

经典排序算法解析

珲少
 珲少
发布于 2017/03/24 16:25
字数 4361
阅读 102
收藏 3

经典排序算法解析

    许多高级语言中都提供有排序函数,但是掌握一些经典排序算法的基本原理和编码方法还是很有必要,这个学习过程可以帮助我们更好的理解每种排序算法的设计思路,本篇博客将介绍9种十分经典的排序算法,提供了解释性语言JavaScript与编译型语言C的源代码。

一、直接插入排序

    直接插入排序是最简单的一种排序算法,也最容易理解。它的核心思想为将元素逐个插入一个有序的数列中。用文字描述可以分为如下几步:

1.把数列中的第一个元素取出,作为有序数列的起始元素。

2.依次拿数列中的其他元素与有序数列中的元素进行比较,将其插入正确的位置。

用图示描述插入排序如下:

直接插入排序的特点是对新元素的每轮插入前,有序数列中的所有元素都是排序好的,即任意时刻,被排序动过的元素组成的数列都是有序的。

用JavaScript实现的简单插入排序:

//插入排序
var array = [1,54,2,64,12,65,76,46,34,98];
for(var i = 0;i<array.length-1;i++){
	var temp = array[i+1];
	for(var j = i+1;j>0;j--){
		if (temp<array[j]) {
			array[j+1] = array[j];
			array[j] = temp;
		}
	}
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

用C实现的简单插入排序:

#include <stdio.h>
void mySort(int array[],int size){
	for(int i=0;i<size-1;i++){
		int temp = array[i+1];
		for(int j=i+1;j>0;j--){
			if(temp<array[j]){
				array[j+1] = array[j];
				array[j] = temp;
			}
		}	
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
	mySort(a,10);
	for(int i = 0;i<10;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

二、二分插入排序(折半插入排序)

    二分插入排序也是插入排序的一种,其又叫做折半插入排序。它与直接插入排序的唯一不同只在于查找插入位置的方式。直接插入排序是通过遍历来查找要插入元素的位置,二分插入排序则是通过二分法来查找要插入的位置,之后将此位置所有元素后移,将排序的元素进行插入。

JavaScript实现的二分插入排序:

var array = [1,54,2,64,12,65,76,46,34,98];
//二分插入排序
for(var i=0;i<array.length-1;i++){
	var temp = array[i+1];
	var left = 0;
	var right = i;
	var middle;
	while(left<=right){
		middle = Math.round((left+right)/2);
		if (array[middle]>temp) {
			right=middle-1;
		}else{
			left = middle+1;
		}
	}
	for(var j=i+1;j>left;j--){
		array[j] = array[j-1];
	}
	array[left] = temp;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];

C实现的二分插入排序:

#include <stdio.h>
//二分插入排序
void mySort(int array[],int size){
	for(int i=0;i<size-1;i++){
		int temp = array[i+1];
		int left=0,right=i,middle;
		while(left<=right){
			middle = (left+right)/2;
			if(array[middle]>temp){
				right=middle-1;
			}else {
				left = middle+1;
			}
		}
		for(int j =i+1;j>left;j--){
			array[j] = array[j-1];
		}	
		array[left] = temp;
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
	mySort(a,10);
	for(int i = 0;i<10;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

三、希尔排序

    希尔排序也是插入排序的一种,它先将整个数列分割成若干个小的子序列进行插入排序,逐渐减少子序列的个数,直到最后组合成一个数列,完成整个排序过程。希尔排序的过程使用文字描述可以表示为如下几步:

1.假设数列元素个数为n,先取一个小于n的增量d1,将所有间隔d1距离的元素放为1组进行插入排序,d1通常取值n/2,向下取整。

2.再次取d2<d1,将所有间隔d2距离的元素放为1组进行插入排序,通常d2取值为d1/2,向下取整。

3.重复步骤2,直到取得d等于1。

图示希尔排序如下:

JavaScript实现的希尔排序:

var array = [1,54,2,64,12,65,76,46,34,98];
//希尔排序
//步长 分组数
var d = Math.floor(array.length/2);
while(d>=1){
	//每组元素个数
	var counts = Math.floor(array.length/d);
	//每组排序依次
	for (var i = 0; i < d ; i++) {
		//组内的插入排序
		for(var j = 0;j<counts-1;j++){
			var temp = array[(j+1)*d];
			for(var k = ((j+1)*d);k>0;k-=d){
				if (temp<array[k]) {
					array[k+d] = array[k];
					array[k] = temp;
				}
			}
		}
	}
	//重取d值
	d=Math.floor(d/2);
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];

C实现的希尔排序:

#include <stdio.h>
//希尔排序
void mySort(int array[],int size){
	int d = size/2;
	while(d>=1){
	//每组元素个数
	int counts = size/d;
	//每组排序依次
	for (int i = 0; i < d ; i++) {
		//组内的插入排序
		for(int j = 0;j<counts-1;j++){
			int temp = array[(j+1)*d];
			for(int k = ((j+1)*d);k>0;k-=d){
				if (temp<array[k]) {
					array[k+d] = array[k];
					array[k] = temp;
				}
			}
		}
	}
	//重取d值
	d=d/2;
}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
	mySort(a,10);
	for(int i = 0;i<10;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

四、选择排序

        前边所说的3种排序算法原理上都是插入排序,即从无序数列中逐个取元素将其插入到有序数列中的合适位置。选择排序则刚好与之相反,其从无序数列中先找到最小值,放在排序数列首部,在依次找到剩余数列的中最小值追加入有序数列,最终完成数列的排序。用文字描述选择排序步骤不如:

1.找到数列中的最小值,将其作为有序数列的第一个元素。

2.从剩余数列中找到最小值,追加入有序数列。

3.重复步骤2,直到排完整个数列。

图示描述选择排序如下:

JavaScript实现的选择排序算法:

var array = [1,54,2,64,12,65,76,46,34,98];
//选择排序
for(var i=0;i<array.length-1;i++){
	//找到最小值
	var min = array[i];
	var index = i;
	for (var j = i+1; j <array.length; j++) {
		if (array[j]<min) {
			min = array[j];
			index = j;
		}
	}
	//进行交换
	array[index]=array[i];
	array[i]=min;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C实现的选择排序算法:

//选择排序
void mySort(int array[],int size){
	for(int i=0;i<size-1;i++){
		int min = array[i];
		int index = i;
		for(int j=i+1;j<size;j++){
			if(array[j]<min){
				min = array[j];
				index = j;
			}
		}
		array[index] = array[i];
		array[i]=min;	
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
	mySort(a,11);
	for(int i = 0;i<10;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

五、冒泡排序

      冒泡排序和选择排序是我们学习编程课时必不可少的两种排序算法,冒泡排序算法的核心是每次比较相邻的连个元素,如果它们的顺序不对,则进行交换,一轮排序下来,最大值一定被排序到数列的末端。之后除去最后一个元素再进行第二轮冒泡,直到整个数列排序完成。用文字描述冒泡排序的过程如下:

1.从左向右依次比较相邻两元素,如果顺序不对,则进行交换,最终最大的元素被放在最后。

2.除去最后一个元素,重复步骤1,最终剩下元素中最大的被放在倒数第2个位置。

3.继续上面的重复,直到排完整个数列。

JavaScript实现的冒泡排序算法:

var array = [1,54,2,64,12,65,76,46,34,98];
//冒泡排序
for(var i=0;i<array.length-1;i++){
	for(var j=0;j<array.length-i-1;j++){
		var temp = array[j];
		if (temp>array[j+1]) {
			array[j] = array[j+1];
			array[j+1] = temp;
		}
	}
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C实现的冒泡排序算法:

#include <stdio.h>
//冒泡排序
void mySort(int array[],int size){
	for(int i =0;i<size-1;i++){
		for(int j=0;j<size-1-i;j++){
			int temp = array[j];
			if(temp>array[j+1]){
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
	mySort(a,10);
	for(int i = 0;i<10;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

六、双向冒泡排序

    双向冒泡排序是冒泡排序的一种变体,冒泡排序每次比较都是从左向右,找出最大的放在最后。双向冒泡排序则是第一轮从左向右将最大的放最后,第二轮从右向左将最小的放最首,如此交替直到整个数列排序完成。文字描述双向冒泡排序步骤如下:

1.从左向右依次比较相邻两个元素,如果顺序不对,则进行交换,如此一轮下来,最大的元素在最后。

2.除去已经排序好的元素,从右向左依次比较相邻的两个元素,如果顺序不对,则进行交换,最小的元素在首部。

3.交替重复步骤1与步骤2直到排序完成。

双向冒泡排序示意图如下:

JavaScript实现的双向冒泡排序算法:

var array = [1,54,2,64,12,65,76,46,34,98];
//双向冒泡排序
var start = 0;
var end = array.length;
while(end-start>0){
	//从左向右冒泡
	for(var i=start;i<end-1;i++){
		var temp = array[i];
		if (array[i+1]<temp) {
			array[i] = array[i+1];
			array[i+1] = temp;
		}
	}
	end--;
	//从右向左冒泡
	for(var j=end;j>start+1;j--){
		var temp = array[j];
		if (array[j-1]>temp) {
			array[j] = array[j-1];
			array[j-1] = temp;
		}
	}
	start++;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C实现的双向冒泡排序算法:

#include <stdio.h>
//双向冒泡排序
void mySort(int array[],int size){
	int start = 0;
	int end = size;
	//从左向右冒泡
	for(int i=start;i<end-1;i++){
		int temp = array[i];
		if (array[i+1]<temp) {
			array[i] = array[i+1];
			array[i+1] = temp;
		}
	}
	end--;
	//从右向左冒泡
	for(int j=end;j>start+1;j--){
		int temp = array[j];
		if (array[j-1]>temp) {
			array[j] = array[j-1];
			array[j-1] = temp;
		}
	}
	start++;
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,33};
	mySort(a,11);
	for(int i = 0;i<11;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

七、快速排序算法

    快速排序算法和基本思路是通过一趟排序将数列分成两部分,其中一部分的所有数据都比另一部分小。之后在分别在两个子数列中进行递归,直到最终排序完成。快速排序算法的核心是递归,因此其效率十分高。用文字描述快速排序的步骤如下:

1.随机取一个元素作为基准,将小于此元素的数据都放在此元素的左侧,大于此元素的数据都放在此元素的右侧,将数列分隔成左右两个子数列。

2.分别对左右子数列进行步骤1的递归,直到数列长度为1或者0,表示排序完成。

JavaScript实现的快速排序算法:

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//快速排序
function sort(array, left, right) {
	if (right - left >= 1) {
		//取第一个元素作为基准
		let base = array[left];
		let i = left + 1;
		let index = left;
		while (i <= right) {
			//大于等于的已经在右边 不需要修改 小于的要放在左边
			if (array[i] < base) {
				if (index + 1 == i) {
					//交换
					array[index] = array[i];
					array[i] = base;
					index++;
				} else {
					//先将base与其后一个元素交换
					array[index] = array[index + 1];
					array[index + 1] = base;
					//交换
					let temp = array[index];
					array[index] = array[i];
					array[i] = temp;
					index++;
				}

			}
			i++;
		}
		//递归排序
		sort(array, left, index - 1);
		sort(array, index + 1, right);
	}
}
sort(array, 0, array.length - 1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C语言实现的快速排序:

#include <stdio.h>
//快速排序
void mySort(int array[],int left,int right){
	if(right-left>=1){
		int base = array[left];
		int i = left+1;
		int index = left;
		while(i<=right){
			if(array[i]<base){
				if(index+1==i){
					array[index] = array[i];
					array[i]=base;
					index = i;
				}else{
					array[index]=array[index+1];
					array[index+1] = base;
					int temp = array[index];
					array[index] = array[i];
					array[i] = temp;
					index++;
				}
			}
			i++;
		}
		mySort(array, left, index-1);
		mySort(array, index+1, right);
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
	mySort(a,0,10);
	for(int i = 0;i<11;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

八、堆排序

    堆排序是比快速排序更加复杂的一种排序算法。堆排序使用到了堆这样一种数据结构。首先我们需要搞清楚什么是堆结构。堆是一种类似完全二叉树,同时又满足如下条件的数据结构:所有子节点的值总是小于(大于)父节点。所有子节点的值都小于父节点的堆叫大顶堆,所有子节点都大于父节点的堆叫小顶堆。

    二叉树你应该比较熟悉,下图就是一个小顶堆的示例:

此二叉树中任何一个子节点的值都是大于父节点。如何将数列构造成这样一个堆结构呢,其实十分简单,将数列按照从上到下,从左到右的原则来构造完全二叉树即可。例如如下数列[1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34]如果将其构造成堆如下图所示:

正常情况下,这个由数组映射成的二叉树并不符合我们堆的要求,否则也就不需要我们用算法来排序了。要让这个二叉树符合要求,我们需要进行整理,即从末节点开始进行调整,例如先从12,98,34中找到最小的,放在现在12所在的位置,然后从64,46,34中找到最小的元素进行上浮,接着再一层层上浮上去,直到堆顶元素为所有元素中的最小元素。整理完成后,我们只需要将堆顶元素和最后一个元素进行交换,之后除掉最后一个元素再进行堆整理,整理完成后再将顶元素(此时为第2小)与倒数第二个元素交换,依次进行下去,即可完成数列的排序。

    用文字描述堆排序步骤如下:

1.先将数列整理成符合要求的堆。

2.将首末元素交换。

3.除掉最后一个元素在进行堆的整理。

4.重复进行2和3,直到数列排序完成。

JavaScript实现的堆排序算法:

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//堆排序
//堆调整 大顶
function store(array,index,end){
	let top = array[index];
	let left;
	let right;
	if (index*2+1<=end) {
		left = index*2+1;
	}else{
		//没有左子树 说明已经是叶子节点
		//无需调整直接return
		return;
	}
	if (index*2+2<=end) {
		right = index*2+2;
	}else{
		//没有右子树 调整左子树即可
		if (array[left]>top) {
			array[index] = array[left];
			array[left] = top;
			top = array[index];
		}
		return;
	}
	//找出堆单元中的最大值
	if (array[left]>top) {
		array[index] = array[left];
		array[left] = top;
		top = array[index];		
	}
	if (array[right]>top) {
		array[index] = array[right];
		array[right] = top;
		top = array[index];
	}
}
function sort(array,end){
	//先将堆进行调整 倒叙调整
	let i = end;
	while(i>=0){
		store(array,i,end)
		i--;
	}
	//根节点一定是最大的 放最后 再进行堆整理
	let temp = array[end];
	array[end] = array[0];
	array[0] = temp;
	end--;
	if (end>0) {
		sort(array,end);
	}else{
		return;
	}
	
}
sort(array, array.length-1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C语言实现的堆排序算法:

#include <stdio.h>
void store(int array[],int index,int end){
	int top = array[index];
	int left;
	int right;
	if (index*2+1<=end) {
		left = index*2+1;
	}else{
		//没有左子树 说明已经是叶子节点
		//无需调整直接return
		return;
	}
	if (index*2+2<=end) {
		right = index*2+2;
	}else{
		//没有右子树 调整左子树即可
		if (array[left]>top) {
			array[index] = array[left];
			array[left] = top;
			top = array[index];
		}
		return;
	}
	//找出堆单元中的最大值
	if (array[left]>top) {
		array[index] = array[left];
		array[left] = top;
		top = array[index];		
	}
	if (array[right]>top) {
		array[index] = array[right];
		array[right] = top;
		top = array[index];
	}
}
void mySort(int array[],int end){
	//先将堆进行调整 倒叙调整
	int i = end;
	while(i>=0){
		store(array,i,end);
		i--;
	}
	//根节点一定是最大的 放最后 再进行堆整理
	int temp = array[end];
	array[end] = array[0];
	array[0] = temp;
	end--;
	if (end>0) {
		mySort(array,end);
	}else{
		return;
	}
	
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
	mySort(a,10);
	for(int i = 0;i<11;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

需要注意,大顶堆排序完成后为升序,小顶堆排序完成后为降序。

九、归并排序

    归并排序的核心并不是交换元素的顺序,而是将数列分成多个有序小数列,将相邻的小数列进行归并。文字描述归并排序步骤如下:

1.把长度为n的数列分成长度为1的n个数列。

2.相邻数列进行排序归并。

3.重复操作2,直到所有数列归并成1个整体。

JavaScript实现的归并排序算法:

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//归并排序
function mergeArray(arrL,arrR){
	var tempArray = new Array();
	let i = 0;
	let j = 0;
	while(i<arrL.length && j<arrR.length){
		if (arrL[i]<arrR[j]) {
			tempArray.push(arrL[i]);
			i++;
		}else{
			tempArray.push(arrR[j]);
			j++;
		}
	}
	while(i<arrL.length){
		tempArray.push(arrL[i]);
		i++;
	}
	while(j<arrR.length){
		tempArray.push(arrR[j]);
		j++
	}
	return tempArray;
}
function sort(array){
	if (array.length>1) {
		let arrL = array.slice(0,Math.floor(array.length/2));
		let arrR = array.slice(Math.floor(array.length/2),array.length);
		if (arrL.length>1) {
			arrL = sort(arrL);
		}
		if (arrR.length>1) {
			arrR = sort(arrR);
		}
		return mergeArray(arrL,arrR);	
	}
	return array;
}
console.log(sort(array)); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C语言实现的归并排序算法:

#include <stdio.h>
void merge(int array[],int temp[],int start,int end,int middle){
	int i=start,j=middle+1,k=start;
	while(i<middle+1 && j<end+1){
		if(array[i]<array[j]){
			temp[k++] = array[i++];
		}else {
			temp[k++] = array[j++];
		}
	}
	while(i<middle+1){
		temp[k++] = array[i++];
	}
	while(j<end+1){
		temp[k++] = array[j++];
	}
	for(i=start;i<=end;i++){
		array[i] = temp[i];
		// printf("%d,",temp[i]);	
	}
}
void sort(int array[],int temp[],int start,int end){
	int middle;
	if(start<end){
		middle = (start+end)/2;
		sort(array, temp, start, middle);
		sort(array, temp, middle+1, end);
		merge(array, temp, start, end, middle);
	}
}
int main(){
	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
	int b[11] = {0};
	sort(a,b,0,10);
	for(int i = 0;i<11;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

 

© 著作权归作者所有

珲少

珲少

粉丝 873
博文 390
码字总数 469911
作品 0
上海
iOS工程师
私信 提问
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
经典排序之 冒泡排序

Author: bakari Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为冒泡排序。 冒泡排序是最古老的排序,我们最早...

chambai
2012/08/11
0
0
Python大牛的必学成长之路(20个经典学习资料)

想要成为Python大师,首先要从最基础知识开始学起,了解掌握Python最基础的知识点,编程意识从无都有,才能在Python 的道路上走得更远。 第一章 python基础 3课时 1小时5分钟 1、python 入门...

让往事随风
2015/12/23
26
0
经典排序之 堆排序

Author: bakari Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为堆排序。 堆排序是运用二叉树建立的一种排序方...

chambai
2012/08/11
0
0
经典排序之 快速排序

Author: bakari Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为快排。 快排是一个非常重要的算法,在各个领域...

chambai
2012/08/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分享一波 RabbitMQ 面试题有答案

1、什么是rabbitmq 2、为什么要使用rabbitmq 3、使用rabbitmq的场景 4、如何确保消息正确地发送至RabbitMQ? 如何确保消息接收方消费了消息? 发送方确认模式 接收方确认机制 接收方消息确认...

搜云库技术团队
52分钟前
2
0
2019年JAVA面试题(高级资深)

记录下本年度最新的面试题: 2019-04-24 //某互联网公司,劳工资源管理方向职位 1.bio/nio/aio介绍下,粘包、拆包问题怎么解决? 2.数据库四个特性是什么,事务传播性是怎么样的?spring事务和...

em_aaron
55分钟前
1
0
yarn如何全局安装命令以及和环境变量的关系

npm全局安装 npm i -g xxx yarn 全局安装 yarn global add xxx 然而你可能会发现npm全局安装后的命令可以直接使用,而yarn却不行,这是为什么呢? 我们来查看下npm和yarn的bin目录 使用npm全...

单线程生物
今天
2
0
异步线程RequestContextHolder.getRequestAttributes()为null

使用Spring框架,在Service中开启一个新的线程,在新的线程中使用 RequestAttributes ra = RequestContextHolder.getRequestAttributes(); 获取出来为null,有没有什么办法能解决? 问题出现...

xiaomin0322
今天
1
0
mingw64环境搭建

mingw64环境搭建 转自:http://www.cr173.com/soft/132367.html MinGW64位版,默认编译出来是64位的,需要编译32位请使用-m32 参数!mingw是一款gnu工具集合是Minimalist GNU on Windows的简称...

shzwork
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部