几种排序算法的原理以及 Java 实现 _排序算法

一、概述：
本文给出常见的几种排序算法的原理以及 JAVA 实现，包括常见的简单排序和高级排序算法，以及其他常用的算法知识。

简单排序：冒泡排序、选择排序、插入排序
高级排序：快速排序、归并排序、希尔排序
相关算法知识：划分、递归、二分查找

二、冒泡排序：
（1）原理：

从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
重复上述过程，没排完一轮，比较次数就减少一次。

（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）原理：

将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；
此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大；
指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

（2）例子：
待比较数据：7, 6, 9, 8, 5,1