欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

各类排序算法总结(Java代码实现)

程序员文章站 2024-03-17 22:04:40
...

一、   稳定性

稳定性是指待排序的序列中有两个或者两个以上相同的项,排序前和排序后,看这些相同的项的相对位置有没有没发生变化,如果没有发生变化,就是稳定的;如果发生变化,就是不稳定的。

二、   排序分类以及复杂度

2.1、      插入类排序

2.1.1、直接插入排序

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n)

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

空间复杂度:O(1)

2.1.2、折半插入排序

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n)

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

空间复杂度:O(1)

2.1.3、希尔排序

平均时间复杂度:O(nlogn)

空间复杂度:O(1)

2.2、      交换类排序

2.2.1、冒泡排序

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n)

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

空间复杂度:O(1)

2.2.2、快速排序

最坏时间复杂度:O(n^2)

最好时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

空间复杂度:O(logn)

2.3、      选择类排序

2.3.1、简单选择排序

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n^2)

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

空间复杂度:O(1)

2.3.2、堆排序

最坏时间复杂度:O(nlogn)

最好时间复杂度:0(nlogn)

平均时间复杂度:O(nlogn)

空间复杂度:O(1)

2.4、      归并类排序

2.4.1、二路归并排序

最坏时间复杂度:O(nlogn)

最好时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

空间复杂度:O(n)

2.5、      基数类排序

最坏时间复杂度:O(d(n+rd))

最好时间复杂度:

平均时间复杂度:O(d(n+rd))

空间复杂度:O(rd)

三、   各类排序算法Java代码

3.1、      直接插入排序

介绍和思想

介绍:插入排序基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。

思想:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

算法代码

public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
		int j;
		for (int i = 1; i < a.length; i++) {
			T tmp = a[i];
			for (j = i; j > 0 && tmp.compareTo(a[j-1])<0; j--) {
				a[j] = a[j-1];
			}
			a[j] = tmp;
		}
	}

3.2、      折半插入排序

介绍和思想

折半插入排序的基本思想和直接插入排序一样,区别在于寻找插入位置的方法不同,折半插入排序是采用折半查找方法类寻找插入位置的。

算法代码

public static void binaryInsertSort(int[] a) {
		for(int i = 1;i < a.length;i++) {
			int temp = a[i];
			int low = 0;
			int high = i-1;
			while(low<=high) {
				int mid = (low+high)/2;
				if(temp < a[mid]) {
					high = mid-1;
				}else {
					low = mid+1;
				}
			}
			for(int j = i;j>=low+1;j--) {
				a[j] = a[j-1];
			}
			a[low] = temp;
		}
	}

3.3、      冒泡排序

算法介绍和思想

冒泡排序是通过一系列的“交换”动作完成的,是交换类排序的一种。

首先第一个记录和第二个记录比较,如果第一个大,则两者交换,否则不交换;

然后第二个记录和第三个记录比较,如果第二个大,则两者交换,否则不交换……一直按这种方式进行下去,最终最大的那个记录被交换到了最后,一趟冒泡排序完成。

然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,使关键字次大的记录被安置到第n-1个记录的位置上……一直这样进行下去,直到在一趟排序过程中没有进行过交换记录的操作,这也是冒泡排序算法的结束条件

算法代码
public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
		int i,j,flag;
		T temp;
		for(i=a.length-1;i>0;i--) {//最多进行a.length-1趟排序
			flag = 0;
			for(j=0;j<i;j++) {////对当前无序区间a[0......i]进行排序
				if(a[j].compareTo(a[j+1])>0) {//大值交换到后面
					temp = a[j+1];
					a[j+1] = a[j];
					a[j] = temp;
					flag = 1;
				}
			}
			if(flag == 0) {//结束条件:某一趟排序是否有交换
				return;
			}
		}
	}

3.4、      快速排序

算法介绍和思想

快速排序是对冒泡排序的一种改进,它也是“交换”类排序的一种。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序

算法步骤和过程

一趟快速排序的具体做法是:附设两个指针low和high,它们的初值分别为low和high,设枢轴记录的关键字为pivotkey,则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录互相交换,重复这两步直至low=high为止。

实质上,快速排序就三个步骤:

第一步:将待排序序列一分为二

第二步:对小于pivotkey的低子表递归排序

第三步:对大于pivotkey的高子表递归排序

算法代码
/**
 * 第一步:将待排序序列一分为二
 * 第二步: 对低子表递归排序
 * 第三步:对高子表递归排序
 * @author 卡罗-晨
 */
public class QuickSort {
	
	/**
	 * 将序列一分为二,并返回枢轴位置
	 */
	private static <T extends Comparable<? super T>> int partition(T[] a,int low,int high) {
		T pivotkey = a[low];
		while(low<high) {
			while(low<high && a[high].compareTo(pivotkey)>=0) --high;
			a[low] = a[high];
			while(low<high && a[low].compareTo(pivotkey)<=0) ++low;
			a[high] = a[low];
		}
		a[low] = pivotkey;
		return low;
	}
	
	/**
	 * 快速排序三步走
	 */
	private static <T extends Comparable<? super T>> void qSort(T[] a,int low,int high) {
		if(low<high) {
			int pivotloc = partition(a, low, high);
			qSort(a, low, pivotloc-1);
			qSort(a, pivotloc+1, high);
		}
	}
	public static <T extends Comparable<? super T>> void quickSort(T[] a) {
		qSort(a, 0, a.length-1);
	}
}

一个方法实现快速排序

public static void quickSort(int[] a,int low,int high) {
		int temp;
		int i = low,j = high;
		if(low < high) {
			temp = a[low];
			while(i != j) {
				while(j>i&&a[j]>=temp) --j;
				if(i<j) {
					a[i] = a[j];
					++i;
				}
				while(i<j&&a[i]<=temp) ++i;
				if(i<j) {
					a[j] = a[i];
					--j;
				}
				a[i] = temp;
				quickSort(a, low, i-1);
				quickSort(a, i+1, high);
			}
		}
	}

3.5、      简单选择排序

算法介绍和思想

选择类排序的主要动作是“选择”,简单选择排序采用最简单的选择方式,从头至尾扫描序列,找出最小的一个记录,和第一个记录交换,接着从剩下的记录中继续这种选择和交换吗,最终使序列有序。

算法代码

public static void selectSort(int[] a) {
		int minIndex;
		int temp;
		for(int i = 0;i<a.length;i++) {
			minIndex = i;
			for(int j = i+1;j<a.length;j++) {
				if(a[j]<a[minIndex]) {
					minIndex = j;
				}
			}
			if(minIndex != i) {
				temp = a[i];
				a[i] = a[minIndex];
				a[minIndex] = temp;
			}
		}
	}

3.6、      堆排序

算法介绍

是一种数据结构,可以把堆看成一棵完全二叉树,这棵完全二叉树满足:任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小,叫大顶堆;若父亲小孩子大,则这样的堆叫做小顶堆

二叉树:每个结点最多只有两棵子树,即二叉树中结点的度只能为0、1、2。子树有左右之分,不能颠倒。

满二叉树:在一棵二叉树中,如果所有的分支结点都有左孩子和右孩子结点,并且叶子结点都集中在二叉树的最下一层。另一种定义:一棵深度为k且有 个结点的二叉树称为满二叉树。

完全二叉树:深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。通俗来讲,一棵完全二叉树是由一棵满二叉树从右至左从下而上,挨个删除结点所得到的。

堆排序的思想:将一个无序序列调整为一个堆,就可以找出这个序列的最大(或最小)值,然后将找出的这个值交换到序列的最后(或最前),这样有序序列元素增加·个,无序序列中元素减少1个,对新的无序序列重复这样的操作,就实现了排序。

堆排序的过程(自述):

1)首先,建堆:原始序列对应一个还不是堆的完全二叉树。对非叶子节点从右至左,从下至上,进行下滤操作,得到一个大顶堆。

待下滤操作的第一个非叶子节点计算方法:a.length/2-1

下滤操作思想:首先判断非叶子节点是否为两个孩子,两个孩子谁更大,指针指向大孩子;接着,判断非叶子节点和指针指向的大孩子谁更大,孩子大则交换。

2)接着,排序:将大顶堆堆顶和无序序列最后一个记录交换,有序+1记录,无序-1记录。

3)然后,将交换后的完全二叉树,从堆顶下滤,将其调整为一个大顶堆,重复上述过程。直到树中只剩下1个节点时排序完成。

堆排序执行过程

l  将原始序列化为一个完全二叉树。

l  从无序序列所确定的完全二叉树的第一个非叶子结点开始,从右至左,从下至上,对每一个结点进行调整,最终将得到一个大顶堆。

对结点的调整方法:将当前结点(假设为a)的值与其孩子结点进行比较,如果存在大于a值的孩子结点,则从中选出最大的一个与a交换。当a来到下一层的时候重复上述过程,直到a的孩子结点值都小于a的值为止。

l  将当前无序序列中第一个元素,反映在树中是根节点(假设为a)与无序序列中最后一个元素交换(假设为b)。a进入有序序列,到达最终位置。无序序列中元素减少1个,有序序列中元素增加1个。此时只有结点b可能不满足堆的定义,对其进行调整。

l  重复3)中的过程,知道无序序列中的元素剩下1个时排序结束

算法代码(Java)

/**
 * 堆排序
 * @author 卡罗-晨
 */
public class HeapSort {

	public static int leftChild(int i) {
		return 2*i+1;
	}
	
	private static <T extends Comparable<? super T>> void percDown(T[] a,int i,int n) {
		int child;
		T tmp;
		for (tmp = a[i];leftChild(i)<n;i=child) {
			child = leftChild(i);
			if(child != n-1 && a[child].compareTo(a[child+1])<0) {
				child++;
			}
			if(tmp.compareTo(a[child])<0) {
				a[i] = a[child];
			}else 
				break;
		}
		a[i] = tmp;
	}
	/**
	 * 标准堆排序
	 * @param a可比较的集合
	 */
	public static <T extends Comparable<? super T>> void heapsort(T[] a) {
		//建立堆
		for(int i=a.length/2-1;i>=0;i--) {
			percDown(a, i, a.length);
		}
		for(int i=a.length-1;i>0;i--) {
			T tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			percDown(a, 0, i);
		}
	}
}

3.7、      二路归并排序

算法描述

归并排序(MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

若将两个有序表合并成一个有序表,称为二路归并

算法思想

1、  划分:将待排序序列划分为两个长度相等的子序列。

2、  求解子问题:分别对这两个子序列进行归并排序,得到两个有序子序列。

3、  合并:将两个有序子序列合并成一个有序序列。

算法核心步骤

核心步骤就一下三步:

1、归并排序前半个子序列

2、归并排序后半个子序列

3、合并两个已排序的子序列

其中,前两个步骤的是一样的方法mergeSort()进行递归,第三步是另一个方法merge()。这个算法中基本的操作就是第三步合并两个已排序的表。因为这两个表是已排序的,所以若将输出放到第三个表中,则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B,一个输出数组C,以及3个计数器Actr、Bctr、Cctr,它们初始置于对应数组的开始端。A[Actr]和B[Bctr]中较小者被拷贝到C中的下一个位置,相关的计数器向前推进一步。当两个输入表有一个用完的时候,则将另一个表中剩余部分拷贝到C中。

实现代码
public class MergeSortExample {
	public static void mergeSort(int[] a) {
		int[] tempArray = new int[a.length];
		mergeSort(a, tempArray, 0, a.length - 1);
	}
	private static void mergeSort(int[] a, int[] tempArray, int left, int right) {
		if (left < right) {
			int center = (left + right) / 2;
			mergeSort(a, tempArray, left, center);
			mergeSort(a, tempArray, center + 1, right);
			merge(a, tempArray, left, center + 1, right);
		}
	}
	private static void merge(int[] a, int[] tempArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos-1;
		int temPos = leftPos;
		int numElements = rightEnd-leftPos+1;
		while(leftPos<=leftEnd && rightPos<=rightEnd) {
			if(a[leftPos] <= a[rightPos]) {
				tempArray[temPos++] = a[leftPos++];
			}else {
				tempArray[temPos++] = a[rightPos++];
			}
		}
		while(leftPos<=leftEnd) {
			tempArray[temPos++] = a[leftPos++];
		}
		while(rightPos <= rightEnd) {
			tempArray[temPos++] = a[rightPos++];
		}
		for(int i=0;i<numElements;i++,rightEnd--) {
			a[rightEnd] = tempArray[rightEnd];
		}
	}
}

merge()方法很精巧。如果对merge的每个递归调用均局部声明一个临时数组,那么在任一时刻就可能有个临时数组处在活动期。精密的考察表明,由于merge是mergeSort的最后一行,因此在任一时刻只需要一个临时数组在活动,而且这个临时数组可以在public型的mergeSort驱动程序中建立。