package cn.xbz;import java.util.Arrays;/*** 各种排序法的演示* @author xbz**/
public class ArraySort {public static void main(String[] args) {int[] arr = {1, 6, 0, -1, 9, -100, 90};// Bubble.sort(arr);//冒泡排序
// Select.sort(arr);//选择排序
// Insert.sort(arr);//插入排序Quick.sort(arr, 0, arr.length - 1);//快速排序System.out.println(Arrays.toString(arr));}
}/*** 冒泡排序法：* 1.从数组开始依次对比相邻两个数的值，若前者较大则将换两者的数据，* 2.然后与下一位进行对比，直到比较到最后一位则找出最大值放在最后。* 3.之后从剩余的数据中再次循环*/
class Bubble {public static void sort(int[] arr) {long l1 = System.currentTimeMillis();/* 排序 *///外层循环，决定一共排几趟for (int i = 0; i < arr.length - 1; i++) {/* 内层循环，决定比较几次 */for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}long l2 = System.currentTimeMillis();System.out.println(l2 - l1);}
}/** 选择排序法* 1.选择数组的第一个数据为假定最小值（arr[minIndex]），* 依次从数组中找出最小的数赋值给arr[minIndex],* 从而找出最小的数据，将之与第一位的数据交换，则第一位的数据不再理会。* 2.再选择数组的第二位为假定最小值，再从剩余的数据中找出最小值与第二位交换，不再理会。* 3.循环往复，直至找到数组的倒数第二位即可（剩下的最后一位即是最大值）*/
class Select {public static void sort(int[] arr) {long l1 = System.currentTimeMillis();/* 外层循环控制交换的次数，即从第一位开始，到倒数第二位结束（arr.length-1） */for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;//选择第一个数据为假定最小值，存储其下标索引/** 内层循环控制排序(i+1)轮后剩余的数据范围，因为排过序的不必理会，* 所以只需要从i的下一位到数组最后寻找出最小值即可*/for (int j = i + 1; j < arr.length; j++) {if (arr[minIndex] > arr[j]) {//若遇见假定最小值大于当前数据(arr[j])的时候，则说明假定最小值不是最小minIndex = j;//再存储当前数据下标作为最小值与剩余数据对比，全部对比完毕后，//minIndex的值就是剩余数据中最小值的索引}}/** 当退出内层for循环时，表示已经遍历并找到最小值的下标，* 此时将该数据与i的位置数据交换，下一轮不再参与对比* （即第一次从所有数据中找到最小值放到数组第一位，第二次从剩余中找到最小值放到第二位，循环往复）*/int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}long l2 = System.currentTimeMillis();System.out.println(l2 - l1);}
}/*** 插入排序法* 1.先从第二个值将值存入insertVal，开始依次与前一个值（arr[i-1]）a对比，* 2.若小于前一个值a，则insertVal应该位于a之前，所以将a值后移一位，* （此时后移位上的值已经存入insertVal中，所以不用担心被覆盖，而此时数组中则有两个a），* 3.然后将insertVal再与往前一个值（arr[i-2]）b做比较，若小于b则继续将b后移，* 直到往前对比，与一个值x对比时insertVal大于x，则说明insertVal应位于x之后，* 将insertVal插入到x之后（index+1），再从插入位置的后一个开始存入insertVal继续比较循环，* 4.直到将最后一个数据插入到合适的位置，则数组排序完毕。* @author soft01**/
class Insert {public static void sort(int[] arr) {for (int i = 1; i < arr.length; i++) {int insertVal = arr[i];//从第二个值开始，先同当前值的前面对比int index = i - 1;//前面一个值的索引while (index >= 0 && insertVal < arr[index]) {//若小于前面一个值，//把前边一个值往后挪一位，再与前面一个值对比arr[index + 1] = arr[index];//此时index+1位置上的值已经存在insertVal中，所以不用担心被覆盖index--;//继续往前对比，若比前面的一个数大（或相等）时退出循环不再比较,}arr[index + 1] = insertVal;//最后将insertVal值在对比完毕后//（此时index所在的值比insertVal值小，而insertVal比之前比的值小）//吧insertVal的值插入该位置，再从insertVal后面的一个值开始继续一轮对比}}
}/*** 快速排序法* 1.通过一趟排序将要排序的数据分割成独立的两部分，* 2.其中一部分的数据都比另外一部分的所有数据都要小，* 3.然后再按此方法对这两部分数据分别进行快速排序，* 4.整个排序过程可以递归进行，以此达到整个数据变成有序序列。* @author soft01**/
class Quick {public static void sort(int[] arr, int low, int high) {int pos;if (low < high) {pos = FindPos(arr, low, high);sort(arr, low, pos - 1);sort(arr, pos + 1, high);}}public static int FindPos(int[] arr, int low, int high) {int val = arr[low];while (low < high) {while (low < high && arr[high] >= val) {--high;}arr[low] = arr[high];while (low < high && arr[low] < val) {++low;}arr[high] = arr[low];}arr[low] = val;return low;}
}另外 , 有人做了一个动画版的各种算法的演示 , 更直观形象 ,大家可以移步观看H5实现各种排序算法动画
