几种常见排序算法的实现[内部排序]

马上要找开始找工作了

 

抽点空对各种排序算法进行一下总结，随手从维基百科上搜索了一下。

 

排序算法大概分这么多种

稳定的

    冒泡排序（bubble sort） — O(n2)
    鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
    插入排序 （insertion sort）— O(n2)
    桶排序 （bucket sort）— O(n); 需要 O(k) 额外空间
    计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
    合并排序 （merge sort）— O(n log n); 需要 O(n) 额外空间
    原地合并排序 — O(n2)
    二叉排序树排序 （Binary tree sort） — O(n log n)期望时间; O(n2)最坏时间; 需要 O(n) 额外空间
    鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
    基数排序 （radix sort）— O(n·k); 需要 O(n) 额外空间
    Gnome 排序 — O(n2)
    图书馆排序 — O(n log n) with high probability, 需要 (1+ε)n 额外空间

[编辑] 不稳定

    选择排序 （selection sort）— O(n2)
    希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
    组合排序 — O(n log n)
    堆排序 （heapsort）— O(n log n)
    平滑排序 — O(n log n)
    快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序
    Introsort — O(n log n)
    Patience sorting — O(n log n + k) 最坏情况时间，需要 额外的 O(n + k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）

[编辑] 不实用的排序算法

    Bogo排序 — O(n × n!) 期望时间，无穷的最坏情况。
    Stupid sort — O(n3); 递归版本需要 O(n2) 额外存储器
    珠排序（Bead sort） — O(n) or O(√n), 但需要特别的硬件
    Pancake sorting — O(n), 但需要特别的硬件

 

这里面有很多我听说过的，很多没听说过的，有些用过的，有些没用过，大部分用java实现了一遍，从中看一下他们的核心思想。

 

一：冒泡排序

大学课程里面第一个排序算法，它的基本思想是每一个不断的遍历数组，每次遍历总是把最大的那个数找出来放到数组的尾部。经过n轮遍历之后，就排序完成。

/**
	 * 实现冒泡泡排序
	 * @return void
	 * @param int[]
	 * 它的原理是每一次都把最大的数放到最后面
	 * */
	@SuppressWarnings("unused")
	private void bubbleSort(int[] array){
		
		//用于临时存数
		int temp = 0;
		for(int i = 1;i<array.length;i++){
			
			for(int j=0;j<array.length-i;j++){
				if(array[j]>array[j+1]){
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}

 

二：插入排序

核心思想是：将一个数插入到一个有序表中，形成一个新的有序表

/**
	 * 实现插入排序
	 * 实现原理是将后面一个数都插入到前面已经排序好的序列中
	 * */
	@SuppressWarnings("unused")
	private void insertSort(int[] array){
		//从头开始遍历
		for(int i = 0;i<array.length;i++){
			int temp = array[i];
			int j = i;
			//确定每一个数的位置
			while(j>=0&&array[j]>temp){
				//如果有大的那么将前面的数向后面移动
				array[j+1] = array[j];
				j--;
			}
			array[j] = temp;
		}
	}

 

三：选择排序

核心思想是：遍历数组找出最大的那个数，然后插入到合适的正确的位置，这个跟冒泡很像

@SuppressWarnings("unused")
	public void chooseSort(int[] array){
		for(int i=0;i<array.length;i++){
		       //先给他一个小点的值
			int max = min;
			//存储那个最大数的位置
			int place = -1;
			for(int j=0;j<array.length-i;j++){
				//找到每一轮的最大的那个数和那个数的位置
				if(array[j]>max){
					max = array[j];
					place = j;
				}
			}
			//然后把它们插入到合适的位置
			array[place] = array[array.length-i-1];
			array[array.length-i] = max;
		}
	}

 

四：堆排序

这是所有排序中我觉得最复杂的一个，核心思想：其实也是找出最大值，然后也是插入到正确位置，只是找出最大值得办法是使用大顶堆，它的根就是最大值，然后与堆的最后一个节点交换，再进行向下堆调，成为一个新堆，这样重复，直到堆为空。

那么步骤是：1：建堆2：交换3：向下堆调

/**
	 * 实现堆排序
	 * 原理：先建立一个大顶堆，将最后一个元素与第一个元素调换然后向下堆调,依次下去就能得到一个有序数组了
	 * 堆：大顶堆
	 * */
	//建堆
	//向下堆调
	@SuppressWarnings("unused")
	private void shiftDown(int[] array,int st,int end){

		int parent = st;
		//这里之所以加1是因为数组的下标从0开始
		int lchild = 2*st+1;
		int rchild = 2*st+2;
		int max = 0,temp = 0;
		while(lchild<end){
			max = lchild;
			if(rchild<end){
				if(array[lchild]<array[rchild]){
					max=rchild;
				}
			}
			if(array[parent]<array[max]){
				//交换数据
				temp = array[parent];
				array[parent] = array[max];
				array[max] = temp;
				
				//进行下一次堆调当然也可以使用递归
				parent = max;
				lchild = 2*parent+1;
				rchild = 2*parent+2;
			}
			else{break;}
		}
	}
	
	//创建堆
	private void createHeap(int[] array){
		
		for(int i=array.length/2-1;i>=0;i--){
			shiftDown(array,i,array.length);
		}
		print(array);
	}
	
	//这里是堆排序的实现
	public void heapSort(int[] array){
		createHeap(array);
		
		int temp = 0;
		for(int i=1;i<array.length;i++){
			
			temp = array[0];
			array[0] = array[array.length-i];
			array[array.length-i] = temp;
			
			shiftDown(array,0, array.length-i-1);
		}
		
	}

 

五：计数排序

核心思想：对于特定元素x来说，如果确定了序列中比其小的元素的个数。那么就能确定x的位置了，a数组中的数都为非负整数。如果有负数，则因该加上一个数，使其为正。

在这个程序中我们创建了两个大数组，一个用于计数，一个用于临时存储。

/**
	 * 计数排序
	 * 对于特定的元素来说，如果确定了序列中比其小的元素的个数，那么就能确定这个元素的位置了
	 * */
	public void countingSort(int[] array){
		//int数组赋值为0
		int[] count = new int[10000];
		int[] copy = new int[10000];
		
		//给count数组赋值
		for(int i=0;i<array.length;i++){
			count[array[i]]=1;
		}
		//得到比count[i]小的数只是用了一种特殊的方式
		//在纸上画一下就知道了
		for(int i=1;i<10000;i++){
			count[i] = count[i]+count[i-1];
		}
		//在合适的地方放上合适的数
		for(int i=array.length-1;i>=0;i--){
			copy[count[array[i]]-1] = array[i];
		}
		//再把排序好的数据放好
		for(int i=0;i<array.length;i++){
			array[i] = copy[i];
		}
	}

 

六：归并排序

归并排序使用了分治的思想，将一个大的排序分为若干个小的排序

归并排序分为自顶向下，自底向上的排序，当然我们熟知的是自顶向下

后者与前者的区别主要在于后者是合并的过程，而前者是划分的过程，前者与快速排序的思想很相像。下面来看一下它的实现过程。

/**
	 * 合并数组的两段
	 * @param array int[]
	 * @param start 
	 * @param end
	 * @param mid
	 * 将两个排序好的数组合并成一个
	 * */
	public void merge(int[] array,int start,int mid,int end){
		
		//一个辅助数组
		int[] comment = new int[10000];
		int s = start,m = mid,index=start;
		while(s<mid&&m<end){
			if(array[s]<=array[m]){
				comment[index] = array[s];
				s++;
			}
			else {
				comment[index] = array[m];
				m++;
			}
			index++;
		}
		//如果前面这个数组被索引完毕
		if(s == mid){
			
			while(m<end){
				comment[index++] = array[m++];
			}
		}else{
			//System.out.println("s=="+s);
			while(s<end){
				comment[index++] = array[s++];
			}
		}
		
		for(int i = start;i<end;i++){
			array[i] = comment[i];
		}
	}
	
	//实现mergeSort归并排序
	public void mergeSort(int[] array){
		int t = 1;
		int start = 0;
		int i = 0;
		
		while(t<=array.length){
			start = t;
			t = 2*start;
			i = 0;
			while((i+t)<=array.length){
				merge(array, i, i+start, i+t);
				i = i+t;
			}
			print(array);
			if(i+start<array.length){
				merge(array, i, i+start, array.length);
			}
		}
	}
	
	
        //这里实现的是自顶向上的排序
	public void mergeSort1(int[] array, int p1, int p3) {
			if((p3-p1) <= 1) return; //判断是否不需要继续递归

			int p2 = (p3 + p1)/2; //计算中间位置p2

			mergeSort1(array,p1,p2); //将p1 ~ p2之间递归排序
			mergeSort1(array,p2,p3); //将p2 ~ p3之间递归排序 
			
			merge(array,p1,p2,p3); //合并p1~p2,p2~p3
	}

 

七：快速排序

快速排序是一个也是典型的分治

/**
	 * 这里是最经典也用的最多的快速排序
	 * 与merge的不同在于它是一个划分的过程
 * */
	private int split(int[] array,int left,int right){
		int key = array[left];
		int temp = 0;
		int low = left+1;
		int high = right;
		while(low<high){
			if(array[low]<=key) low++;
			else if(array[high]>=key) high--;
			else {
				temp = array[low];
				array[low] = array[high];
				array[high] = temp;
				
			}
		}
		array[left] = array[--low];
		array[low] =key;
		
		return low;
		
	}
	//实现快速排序
	public void quickSort(int[] array,int low,int right){
		int devide = 0;
		if(low<right){
			devide = split(array, low, right);
			System.out.println(devide);
			print(array);
			quickSort(array, low, devide-1);
			quickSort(array, devide+1, right);
		}
	}

 

八：希尔排序

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

	/**
	 * 希尔排序
	 * h = h*3+1.初始 h=1 
	 * */
	
	public void shellSort(int[] array){
		 int h = 1;
		    while(h<array.length)
		        h = h*3+1;
		    h = (h-1)/3;
		    while(h>=1)
		    {
		        for(int i=h;i<array.length;i++)
		        {
		           int j = i-h;
		           int key = array[i];
		           while(j>=0&&array[j]>key)
		           {
		                array[j+h] = array[j];
		                j-=h;     
		           } 
		           j+=h;
		           array[j]=key; 
		        }
		        h=(h-1)/3; 
		    }
	}

 

九：基数排序

这个描述起来比较复杂，算是归纳法的一种吧。实现方式就是一下的，没有这么写注释，就是按照十进制位来排序，比如先第一位排序，然后按照第二位，直到最高位，需要比较大的空间开销。

public  void radixSort(int[] number, int d) {
		int k=0;
		int n=1;
		int m=1;
		int[][] temp = new int[number.length][number.length];
		int[] order = new int[number.length];
		while(m <= d) {
			for(int i = 0; i < number.length; i++) {
				int lsd = ((number[i] / n) % 10);
				temp[lsd][order[lsd]] = number[i];
				order[lsd]++;
			}
			for(int i = 0; i < d; i++) {
				if(order[i] != 0)
					for(int j = 0; j < order[i]; j++) {
						number[k] = temp[i][j];
						k++;
					}
				order[i] = 0;
			}
			n *= 10;
			k = 0;
			m++;
		}
	}

 

马上要找工作了，以上的排序算法在大学多多少少都接触过，但很长时间没有用了，有的就忘记了，现在把它们整理一遍。只是对一些常见的排序算法的一个实现，没有仔细的研究各个算法的时间复杂度空间复杂度。