本文共 3640 字，大约阅读时间需要 12 分钟。

数组排序

1.冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
  
  代码实现：

public class MyTest {
       public static void main(String[] args) {
               int[] arr = {
   24, 69, 80, 57, 13, 20, -1, 0};           for (int j = 0; j < arr.length - 1; j++) {
               for (int i = 0; i < arr.length - 1 - j; i++) {
                   if (arr[i] > arr[i + 1]) {
                       int t = arr[i];                    arr[i] = arr[i + 1];                    arr[i + 1] = t;                }            }        }        System.out.println(Arrays.toString(arr));    }

2.选择排序

每次拿一个元素和后面所有得元素挨个比较，小得往前放，经过一轮比交换，最小得元素会出现在最前面，如此往复，整个数组就排好序了。

public class MyTest2 {
       public static void main(String[] args) {
       int[] arr = {
   24, 69, 80, 57, 13,20,50,200,0,-1};               for (int index = 0; index < arr.length-1; index++) {
               for (int i = 1 + index; i < arr.length; i++) {
                   if (arr[index] > arr[i]) {
                        int t = arr[index];                    arr[index] = arr[i];                    arr[i] = t;                }            }        }        System.out.println(Arrays.toString(arr));    }

3.直接插入排序

直接插入排序：每次将后面一个元素，插入到之前得一个有序序列中，使之仍保持有序

代码实现：

public class MyTest3 {
       public static void main(String[] args) //直接插入排序：每次将后面一个元素，插入到之前得一个有序序列中，使之仍保持有序        int[] arr = {
   49，38，65，97，76，13，27};         for (int i = 1; i < arr.length; i++) {
                       int j=i;            while (j>0&&arr[j]

4.快速排序

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现：

public class QuickSort {
           public void quickSort(int[] arr, int start, int end) {
           if (start < end) {
               //获取分区索引            int index = getIndex(arr, start, end);                       quickSort(arr, start, index - 1);            quickSort(arr, index + 1, end);        }    }  private int getIndex(int[] arr, int start, int end) {
           int i = start;        int j = end;             int x = arr[i];        //循环        while (i < j) {
               //从右往左比较            while (i < j && arr[j] >= x) {
                   j--;            }            //从右往左找到比基准数小的数了后，填坑            if (i < j) {
                   //把这个数填到上一个坑位                arr[i] = arr[j];                //让 i++;                i++;            }//从左往右找            while (i < j && arr[i] < x) {
                   i++;            }            // 找比基准数大的数，找到后填坑            if (i < j) {
                   arr[j] = arr[i];                j--;            }        }        //当上面的循环结束后把基准数填到最后一个坑位，也就一基准数为界，分成了左右两部分        arr[i] = x; //把基准数填进去        return i; //返回基准数所在位置的索引    }}

二分法

public class MyTest2 {
       public static void main(String[] args) {
           //查找思想：前提条件：数组元素必须有序，二分查找：每次查找一半        int[] arr = {
   10, 20, 30, 50, 90, 100, 101, 300, 400};        int index = getIndex(arr, 90);        System.out.println("索引是" + index);    }   private static int getIndex(int[] arr, int ele) {
          int minIndex = 0;        int maxIndex = arr.length - 1;        int centerIndex = (minIndex + maxIndex) / 2;        while (minIndex <= maxIndex) {
               if (ele == arr[centerIndex]) {
                   return centerIndex;            } else if (ele > arr[centerIndex]) {
                   minIndex = centerIndex + 1;            } else if (ele < arr[centerIndex]) {
                   maxIndex = centerIndex - 1;            }         centerIndex = (minIndex + maxIndex) / 2;        }        return -1;    }}

转载地址：http://zdfki.baihongyu.com/