七大经典基于比较排序算法【Java实现】
排序 是我们平常常常需要使用的操作， 所谓排序，就是使一串记录，按照此中的某个或某些关键字的大小，递增或递减的排列起来的操作。 这里我们先容七种常用的经典排序，要想明白排序就必须明白每种排序背后的算法思想。 在不同的场景合理地应用不同地排序方法,以便我们能高效地办理标题。接下来每种排序我都从 算法实现，时间复杂度，空间复杂度，稳定性这几个方面进行阐述。
时间复杂度和空间复杂度是数据结构的基础知识，而稳定性需要偏重阐述一下：
https://i-blog.csdnimg.cn/direct/e36431d5afea49478dd34daaeda8383c.png
即不改变相同数值的内部既定次序的排序称为稳定排序。
一.直接插入排序:
1.1插入排序
https://i-blog.csdnimg.cn/direct/653d5a58404e4316ad437d210e40f094.png
/** 时间复杂度:o(n^2)
最坏情况：5 4 3 2 1
最好情况: 1 2 3 4 5 o(n)
如果一组数据越有序，则直接插入排序效率越高
空间复杂度:o(1)
稳定性：稳定排序（>)
如果一个排序本身是稳定的，那么他可以实现为不稳定的
若是不稳定的，则它不能实现为稳定的
*
*/
//默认从小到大,第一个数字默认有序
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array;
int j = i - 1;
for (; j >= 0; j--) {
if (array > tmp) {
array = array;
} else {
array = tmp;
break;
}
}
array = tmp;
}
}
1.2希尔排序（缩小增量排序法）
https://i-blog.csdnimg.cn/direct/8f23d7c76f5b4128b022345592fe661b.png
https://i-blog.csdnimg.cn/direct/4d9187c19bdc4b26bb7269b096a88d24.png
希尔排序可视为直接插入排序的一种优化，其本质是将数据分为多组别，在不同组别内部进行插入排序，随着组别数减少，组别内数据元素趋于有序，效率加快。
/**
* 希尔排序(直接插入排序的一种优化)
* 首先通过gap对所需排序数据分组进行预排序
* gap的取法不一致导致时间复杂度不同
* 当gap越大时，每组数据趋于无序，但数据较少
* 当gap越小时，每组数据越多，但相较趋于有序
* 时间复杂度:就我这种gap取法而言,n*log2n
* 一般来说n^1,3~n^1.5(实验得出）
* 空间复杂度:o(1)
* 稳定性:不稳定
*
* @param array
*/
public static void shellSort(int[] array) {
int gap = array.length;
//时间复杂度:o(log2n)
while (gap > 1) {
//在gap>1之前进行的都是预排序
gap /= 2;//这里仅仅只gap的一种取法，取法不固定
shell(array, gap);//gap可以取到1
}
}
private static void shell(int[] array, int gap) {
//shell的时间复杂度大约为o(n)(可以考虑极端情况)
for (int i = gap; i < array.length; i++) {
//i最后是需要i++的
int tmp = array;
int j = i - gap;
for (; j >= 0; j -= gap) {
if (array > tmp) {
array = array;
} else {
array = tmp;
break;
}
}
array = tmp;
}
}
二.选择排序
2.1选择排序
https://i-blog.csdnimg.cn/direct/a994d187644a4f6794bb1aef5603a532.png
思想简单，但效率不高！
/**
* 选择排序:
* 时间复杂度：o(n^2)
* 和数据是否有序无关
* 空间复杂度:o(1)
* 稳定性:不稳定排序
*
* @param array
*/
public static void selectSort1(int[] array) {
//12,5,2,9,10,7
//i j
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array < array) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
public static void selectSort2(int[] array) {
//12,5,2,9,10,7
//i j
int left = 0;
int right = array.length - 1;
while (left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if (array < array) {
minIndex = i;
}
if (array > array) {
maxIndex = i;
}
}
swap(array, left, minIndex);
//这里有个问题，如果left是最大值的话，它会被交换到minIndex处，则在下一次交换时找不到maxIndex
if (left == maxIndex) {
maxIndex = minIndex;
}
swap(array, right, maxIndex);
left++;
right--;
}
}
private static void swap(int[] array, int i, int minIndex) {
int tmp = array;
array = array;
array = tmp;
}
2.2堆排序（基于树（堆）的数据结构）
https://i-blog.csdnimg.cn/direct/4b9d063ae35245b5ae78f048d72c7561.png
https://i-blog.csdnimg.cn/direct/f911bbe7591d4e6daf132e1695ebdc0a.png
/**堆排序(Heapsort):是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆
来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆。
* 时间复杂度:o(n*logn)
* 空间复杂度:o(1)
* 稳定性:不稳定
* @param array
*/
public static void heapSort(int[] array){
createHeap(array);
int end=array.length-1;
while(end>0){
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createHeap(int[] array) {
for(int parent=(array.length-1-1)/2;parent>=0;parent--){
siftDown(array,parent,array.length);
}
}
/**
* @param array
* @param parent 每棵子树调整的根节点
* @param length 每棵子树调整的结束节点
*/
private static void siftDown(int[] array, int parent, int length) {
int child=2*parent+1;
while(child<length){
if(child+1<length&&array>array){
child++;
}
if(array>array){
swap(array,parent,child);
parent=child;
child=2*parent+1;
}else{
break;
}
}
}
三.互换排序
3.1冒泡排序
最大（小）的数据不停移动到数据末了，就像水泡一样浮出水面。
/**冒泡排序:
*时间复杂度:o(n^2)---优化前
* 优化后可能达到o(n)
* 空间复杂度:o(1)
* 稳定性:稳定排序
* @param array
*/
public static void bubbleSort(int[] array){
//外层循环表示循环趟数
for(int i=0;i< array.length-1;i++){
boolean flag=false;//优化
for(int j=0;j< array.length-1-i;j++){
if(array>array){
swap(array,j,j+1);
flag=true;
}
}
if(!flag){
break;
}
}
}
3.1快速排序(大致分三种partition方法)
https://i-blog.csdnimg.cn/direct/fe76d0ffff0d43a58530659b7380ba8f.png
https://i-blog.csdnimg.cn/direct/a5f2f45a47d449b59ce391bcea23917e.png
以递归左边为例子：
https://i-blog.csdnimg.cn/direct/7b45a8e1ecc84fcca93e9df7e3ea0c21.png
快速排序不实用于数据是完全的次序和逆序的这种极端环境。而适合在数据相对随机的时间使用。由于使用的递归，所以会在栈上开辟空间。
3.1.1Hoare法
/**
* 时间复杂度：
* 最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)
* 9 8 7 6 5 4
* 最好情况：O(N*logN)
* 空间复杂度：
* 最坏情况：O(N)
* 最好情况：O(logN)
* 稳定性：
* 不稳定性
* @param array
*/
public static void quickSort(int[] array){
//为了保证接口统一,所以创建quick方法
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end) {
if(start>=end)return;
int pivot=partitionHoare(array,start,end);//找中间值
quick(array,start,pivot-1);//递归左边
quick(array,pivot+1,end);//递归右边
}
private static int partitionHoare(int[] array, int left, int right) {
int tmp=array;
int tmpLeft=left;
while(left<right){
while(left<right&&array>=tmp){
right--;
}
while(left<right&&array<=tmp){
left++;
}
swap(array,left,right);
}
swap(array,left,tmpLeft);
return left;
//return right;
}
}
挖坑法（最常用，选择题首选)
前后指针法
四.归并排序
测试代码：
public class Test {
public static void orderArray(int[] array){
for(int i=0;i<array.length;i++){
array=i;//顺序
//array= array.length-i-1;//逆序
}
} public static void notorderArray(int[] array){
Random random=new Random();
for(int i=0;i<array.length;i++){
array=random.nextInt(10_0000);
}
}
public static void testSimple(){
int[] array={12,5,2,9,10,7};
System.out.println("排序前:"+ Arrays.toString(array));
Sort.quickSort(array);
System.out.println("排序后："+Arrays.toString(array));
}
public static void testOther(){
int[] array=new int;
//orderArray(array);
notorderArray(array);
testInsertSort(array);
testShellSort(array);
testSelectSort1(array);
testSelectSort2(array);
testHeapSort(array);
testBubbleSort(array);
testQuickSort(array);
}
public static void testInsertSort(int[] array){
//避免测试后数组本身被修改
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.insertSort(array);
long endTime=System.currentTimeMillis();
System.out.println("直接插入排序1时间："+(endTime-startTime));
}
public static void testShellSort(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.shellSort(array);
long endTime=System.currentTimeMillis();
System.out.println("希尔插入排序时间："+(endTime-startTime));
}
public static void testSelectSort1(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.selectSort1(array);
long endTime=System.currentTimeMillis();
System.out.println("选择插入排序1时间："+(endTime-startTime));
}
public static void testSelectSort2(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.selectSort2(array);
long endTime=System.currentTimeMillis();
System.out.println("选择插入排序2时间："+(endTime-startTime));
}
public static void testHeapSort(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.heapSort(array);
long endTime=System.currentTimeMillis();
System.out.println("堆排序时间："+(endTime-startTime));
}
public static void testBubbleSort(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.bubbleSort(array);
long endTime=System.currentTimeMillis();
System.out.println("冒泡排序时间："+(endTime-startTime));
}
public static void testQuickSort(int[] array){
array=Arrays.copyOf(array,array.length);
long startTime=System.currentTimeMillis();
Sort.quickSort(array);
long endTime=System.currentTimeMillis();
System.out.println("快速排序时间："+(endTime-startTime));
}
public static void main(String[] args) {
testSimple();
testOther();
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]