Java 排序算法阐发与实现

发布日期:2019-07-23 19:47:43 阅读数: 276次 来源: 作者:

一、概述:

  

本文给出常见的几种排序算法的道理以和 Java 实现,包罗常见的简单排序和高级排序算法,以和其他常用的算法学问。

  • 简单排序:冒泡排序、选择排序、插入排序
  • 高级排序:快速排序、合并排序、希尔排序
  • 相关算法学问:划分、递归、二分查找

二、冒泡排序:

(1)道理:

  • 1、从第一个数据起头,与第二个数据比拟较,若是第二个数据小于第一个数据,则互换两个数据的位置。
  • 2、指针由第一个数据移向第二个数据,第二个数据与第三个数据比拟较,若是第三个数据小于第二个数据,则互换两个数据的位置。
  • 3、依此类推,完成第一轮排序。第一轮排序竣事后,最大的元素被移到了最左面。
  • 4、按照上面的过程进行第二轮排序,将第二大的排在倒数第二的位置。
  • 5、反复上述过程,没排完一轮,比力次数就削减一次。

(2)例子:

待排序数据:7, 6, 9, 8, 5,1

第一轮排序过程:

指针先指向7,7和6比力,6<7,互换6和7的位置,成果为:6,7,9,8,5,1
指针指向第二个元素7,7和9比力,9>7,不消互换位置,成果仍为:6,7,9,8,5,1
指针指向第三个元素9,比力9和8,8<9,互换8和9的位置,成果为:6,7,8,9,5,1
指针指向第四个元素9,比力9和5,5<9,互换5和9,成果为:6,7,8,5,9,1
指针指向第五个元素9,比力9和1,1<9,互换1和9的位置,成果为6,7,8,5,1,9

第一轮排序竣事后,最大的数字9被移到了最左边。

进行第二轮排序,过程同上,只是因为最大的9曾经放在最左边了,因而不消在比力9了,少了一次比力,第二轮竣事的成果为:6,7,5,1,8,9

第三轮成果:6,5,1,7,8,9

第四轮比力成果:5,1,6,7,8,9

第五轮比力成果:1,5,6,7,8,9

最终排序成果为:1,5,6,7,8,9,由上可知N个数据排序,需要进行N-1轮排序;第i轮排序需要的比力次数为N-i次。

(3)编码思绪:

需要两层轮回,第一层轮回i暗示排序的轮数,第二层轮回j暗示比力的次数。

(4)代码实现:

实例

package com.test.insertsort; /** * 选择排序 * @author Administrator * */ public class ChooseSort { private int[] array; private int length; public ChooseSort(int[] array){ this.array = array; this.length = array.length; } /** * 打印数组中的所有元素 */ public void display(){ for(int i: array){ System.out.print(i+" "); } System.out.println(); } /** * 选择排序算法 */ public void chooseSort(){ for(int i=0; i<length-1; i++){ int minIndex = i; for(int j=minIndex+1;j<length;j++){ if(array[j]<array[minIndex]){ minIndex = j; } } int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } public static void main(String[] args){ int[] array={100,45,36,21,17,13,7}; ChooseSort cs = new ChooseSort(array); System.out.println("排序前的数据为:"); cs.display(); cs.chooseSort(); System.out.println("排序后的数据为:"); cs.display(); } }

(5)选择排序总结:

N个元素需要排序N-1轮;

第i轮需要比力N-i次;

N个元素排序,需要比力n(n-1)/2次;

选择排序的算法复杂度仍为O(n*n);

比拟于冒泡排序,选择排序的互换次数大大削减,因而速度要快于冒泡排序

四、插入排序

插入排序是简单排序中最快的排序算法,虽然时间复杂度仍然为O(n*n),可是却比冒泡排序和选择排序快良多。

(1)道理:

  • 1、将指针指向某个元素,假设该元素左侧的元素全数有序,将该元素抽取出来,然后按照从右往左的挨次别离与其右边的元素比力,碰到比其大的元素便将元素右移,直到找到比该元素小的元素或者找到最左面发觉其左侧的元素都比它大,遏制;
  • 2、此时会呈现一个空位,将该元素放入到空位中,此时该元素左侧的元素都比它小,右侧的元素都比它大;
  • 3、指针向后挪动一位,反复上述过程。每操作一轮,左侧有序元素都添加一个,右侧无序元素都削减一个。

(2)例子:

待比力数据:7, 6, 9, 8, 5,1

  • 第一轮:指针指向第二个元素6,假设6左面的元素为有序的,将6抽离出来,构成7,_,9,8,5,1,从7起头,6和7比力,发觉7>6。将7右移,构成_,7,9,8,5,1,6插入到7前面的空位,成果:6,7,9,8,5,1
  • 第二轮:指针指向第三个元素9,此时其左面的元素6,7为有序的,将9抽离出来,构成6,7,_,8,5,1,从7起头,顺次与9比力,发觉9左侧的元素都比9小,于是无需挪动,把9放到空位中,成果仍为:6,7,9,8,5,1
  • 第三轮:指针指向第四个元素8,此时其左面的元素6,7,9为有序的,将8抽离出来,构成6,7,9,_,5,1,从9起头,顺次与8比力,发觉8
  • 第四轮:指针指向第五个元素5,此时其左面的元素6,7,8,9为有序的,将5抽离出来,构成6,7,8,9,_,1,从9起头顺次与5比力,发觉5比其左侧所有元素都小,5左侧元素全数向右挪动,构成_,6,7,8,9,1,将5放入空位,成果5,6,7,8,9,1。
  • 第五轮:同上,1被移到最左面,最初成果:1,5,6,7,8,9。

(3)编码阐发:

需要两层轮回,第一层轮回index暗示上述例子中的指针,即遍历从坐标为1起头的每一个元素;第二层轮回从leftindex=index-1起头,leftindex--向左遍历,将每一个元素与i处的元素比力,直到j处的元素小于i出的元素或者leftindex

(4)代码实现:

实例

package com.test.insertsort; /** * 插入排序算法: * 1、以数组的某一位作为分隔位,好比index=1,假设左面的都是有序的. * * 2、将index位的数据拿出来,放降临时变量里,这时index位置就空出来了. * * 3、从leftindex=index-1起头将左面的数据与当前index位的数据(即temp)进行比力,若是array[leftindex]>temp, * 则将array[leftindex]后移一位,即array[leftindex+1]=array[leftindex],此时leftindex就空出来了. * * 4、再用index-2(即leftindex=leftindex-1)位的数据和temp比,反复步调3, * 直到找到<=temp的数据或者比到了最左面(申明temp最小),遏制比力,将temp放在当前空的位置上. * * 5、index向后挪1,即index=index+1,temp=array[index],反复步调2-4,直到index=array.length,排序竣事, * 此时数组中的数据即为从小到大的挨次. * * @author bjh * */ public class InsertSort { private int[] array; private int length; public InsertSort(int[] array){ this.array = array; this.length = array.length; } public void display(){ for(int a: array){ System.out.print(a+" "); }亚博手机app System.out.println(); } /** * 插入排序方式 */ public void doInsertSort(){ for(int index = 1; index<length; index++){//外层向右的index,即作为比力对象的数据的index int temp = array[index];//用作比力的数据 int leftindex = index-1; while(leftindex>=0 && array[leftindex]>temp){//当比到最右边或者碰到比temp小的数据时,竣事轮回 array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//把temp放到空位上 } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("排序前的数据为:"); is.display(); is.doInsertSort(); System.out.println("排序后的数据为:"); is.display(); } }

(5)插入排序阐发:

时间复杂度,因为仍然需要两层轮回,插入排序的时间复杂度仍然为O(n*n)。

  比力次数:在第一轮排序中,插入排序最多比力一次;在第二轮排序中插入排序最多比力二次;以此类推,最初一轮排序时,最多比力N-1次,因而插入排序的最多比力次数为1+2+...+N-1=N*(N-1)/2。虽然如斯,现实上插入排序很少会真的比力这么多次,由于一旦发觉左侧有比方针元素小的元素,比力就遏制了,因而,插入排序平均比力次数为N*(N-1)/4。

挪动次数:插入排序的挪动次数与比力次数几乎分歧,但挪动的速度要比互换的速度快得多。

综上,插入排序的速度约比冒泡排序快一倍(比力次数少一倍),比选择排序还要快一些,对于根基有序的数据,插入排序的速度会很快,是简单排序中效率最高的排序算法。


快排、冒泡排序、选择排序、插入排序、合并排序

一、概述:

上文引见了常见简单算法:冒泡排序、选择排序和插入排序。本文引见高级排序算法:快速排序和合并排序。在起头引见算法之前,起首引见高级算法所需要的根本学问:划分、递归,并顺带引见二分查找算法。

二、划分:

划分是快速排序的前提,即把数据分为两组,大于特定值的数据在一组,小于特定值的数据在另一组。快速排序便是由划分和递归操作来完成的。

(1)道理:

定义一个阈值,别离从最左面和最左面向两头遍历元素,左面找到一个大于阈值的数据便遏制,左边找到一个小于阈值的数据便遏制,若是此时摆布两边都还没有走到两头,则互换左面大于阈值的数据和左面小于阈值的数据;反复上述过程,直到左面指针和左面指针相遇,此时左面数据均小于阈值,左面数据均大于阈值,划分竣事。划分竣事后,数据仍然是无序的,但更接近于有序。

(2)例子:

待划分数据:7, 6, 9, 8, 5,1,假设阈值为5

第一轮:左指针指向7,右指针指向1,左指针向后移,右指针向左移,发觉左面第一个大于5的元素7,左面第一个小于5的元素1,互换7和1的位置,成果:1,6,9,8,5,7;

第二轮:从6起头找大于5的数字,找到6,左边从5起找小于5的数字,找到1,但此时因为6在1的左面,,即右指针

(3)代码实现:

实例

package com.test.insertsort; /** * 划分、递归、快排 * @author bjh * */ public class QuickSort { /**待排序、划分数组*/ private int[] array; /**数组长度*/ private int length; public QuickSort(int[] array){ this.array = array; this.length = array.length; } /** * 打印元素 */ public void printArray(){ for(int i=0; i<length; i++){ System.out.print(array[i]+" "); } System.out.println(); } /** * 划分 * @return 划分的分界点 */ public int partition(int left, int right, int pivot){ //左指针的起点,left-1是因为在后面的轮回中,每轮回一次左指针都要右移, //如许能够确保左指针从右边第一个元素起头,否则是从第二个起头 int leftpoint = left-1; //右指针的起点,right+1是因为后面的轮回中,每轮回一次右指针都要左移, //如许能够确保右指针从最左边起头,否则是从倒数第二个起头 int rightpoint = right+1; while(true){ //找到右边大于pivot的数据,或者走到了最左边仍然没有找到比pivot大的数据 while(leftpoint<right && array[++leftpoint]<pivot); //找到左边小于pivot的数据,或者走到了最右边仍然没有找到比pivot小的数据 while(rightpoint>left && array[--rightpoint]>pivot); //左指针和右指针堆叠或订交 if(leftpoint >= rightpoint){ break; }else{ //互换右边大的和左边小的数据 swap(leftpoint,rightpoint); } } //前往分界点,即左边子数组中最右边的点 return leftpoint; } /** * 互换数据 */ public void swap(int leftpoint,int rightpoint){ int temp = array[leftpoint]; array[leftpoint] = array[rightpoint]; array[rightpoint] = temp; } public static void main(String args[]){ int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85}; QuickSort qs = new QuickSort(array); System.out.println("划分前的数据为:"); qs.printArray(); int bound = qs.partition(0, array.length-1, 50); System.out.println("划分后的数据为:"); qs.printArray(); System.out.println("划分的分界点为:" + array[bound] + ",分界点的坐标为:" + bound); } }

运转成果为:

本文由亚博编辑整理亚博手机app