1.直接插入排序

 顾名思义，就是插入，形象的比喻就是摸扑克牌并，整理扑克牌，从牌堆里摸一张，放在手上，再摸一张，和自己手里的对比，大的放后面，小的放前面；再摸一张，和自己最小的对比，依次往后对比。。。。

Java代码：

public void insertSort(int a[]) {    for(int i=1;i
    
     =0&&a[j]>key){            a[j+1]=a[j];            j--;        }        a[j+1]=key;    }}
    

 

2.希尔排序

是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法

解释：

假设有n个元素，先分成两组，每组n/2个元素

        a[i]与a[i+n/2]-------(i=0...n/2)比较

 再分组，四组。每组(n/2)/2个元素

         a[i]与a[i+n/4]-------(i=0...n/2)比较

 

Java代码：

//后往前推    public void shellSort(int a[]) {        for (int gap = a.length / 2; gap > 0; gap /= 2) {            for (int i = 0; i < a.length; i++) {                for (int j = i - gap;j>=0;j -= gap) {                    if (a[j] > a[j + gap]) {                        int temp = a[j];                        a[j] = a[j + gap];                        a[j + gap] = temp;                    }                }            }        }    }    //我的思路    public void shellSortMy(int a[]){        for (int gap = a.length / 2; gap > 0; gap /= 2) {            for (int i = 0; i < gap; i++) {                for (int j = i;j
    
      a[j + gap]) {                        int temp = a[j];                        a[j] = a[j + gap];                        a[j + gap] = temp;                    }                }            }        }
    

3.冒泡排序

很简单，用到的很少，据了解，面试的时候问的比较多！

将序列中所有元素两两比较，将最大的放在最后面。

将剩余序列中所有元素两两比较，将最大的放在最后面。

重复第二步，直到只剩下一个数。

public void bubbleSort(int a[]) {    for (int i = 0; i < a.length - 1; i++) {        for (int j = 0; j < a.length - i - 1; j++) {            if (a[j] > a[j + 1]) {                int tmp = a[j];                a[j] = a[j + 1];                a[j + 1] = tmp;            }        }    }}

代码：

 

4.简单选择排序

解释：冒泡得改进，减少移动次数

常用于取序列中最大最小的几个数时。

(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)

遍历整个序列，将最小的数放在最前面。

遍历剩下的序列，将最小的数放在最前面。

重复第二步，直到只剩下一个数。

 

代码：

public void easySelectSort(int a[]) {    for (int i = 0; i < a.length; i++) {        int position = i;        for (int j = i + 1; j < a.length; j++) {            if (a[position] > a[j]) {                position = j;            }        }        int tmp = a[position];        a[position] = a[i];        a[i] = tmp;    }}

 

5.归并排序

速度仅次于快速排序，内存少的时候使用，可以进行并行计算的时候使用。

选择相邻两个数组成一个有序序列。

选择相邻的两个有序序列组成一个有序序列。

重复第二步，直到全部组成一个有序序列。

public void mergeSort(int a[]) {    int temp[]=new int[a.length];    mergeSort2(a, 0, a.length-1,temp);}public void mergeSort2(int a[], int left, int right,int temp[]) {    if (left < right) {        int mid = (left + right) >> 1;        mergeSort2(a, left, mid,temp);        mergeSort2(a, mid + 1, right,temp);        mergeSort3(a, left, mid, right,temp);    }}public void mergeSort3(int a[], int left, int mid, int right,int temp[]) {    int i = left, j = mid + 1, k = 0;    while (i <= mid && j <= right) {        if (a[i]

6，快速排序

要求时间最快时。

快速排序（Quicksort）是对的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以进行，以此达到整个数据变成有序。

public void quickSort(int a[]) {    quickSort2(a, 0, a.length - 1);}public void quickSort2(int a[], int left, int right) {    int start=left;    int end=right;    int key=a[left];//选择的值    while(end>start){        while(end>start&&a[end]>key){            end--;        }        if(a[end]<=key){            swap(a,end,start);        }        while(end>start&&a[start]<=key){            start++;        }        if(a[start]>=key){            swap(a,start,end);        }    }    if(start>left){        quickSort2(a,left,start-1);    }    if(end

7.堆排序

对简单选择排序的优化。

将序列构建成大顶堆。二分查找树

将根节点与最后一个节点交换，然后断开最后一个节点。

重复第一、二步，直到所有节点断开。

引用：https://www.cnblogs.com/chengxiao/p/6129630.html

思路：先找到最后一个非叶节节点y，比较左右子节点，若果有一个大于y，则互换，y指向较大的子节点。

建堆的第一层循环：找到第一个非叶节点，逐渐向前遍历

jia

//堆排序public void heapSort(int a[]) {    int len = a.length;    //循环建堆    for (int i = 0; i < len - 1; i++) {        //建堆        buildmaxHeap(a, len - 1 - i);        //交换堆顶和最后一个元素        swap(a, 0, len - 1 - i);    }}//对data数组从0到lastIndex建大顶堆public void buildmaxHeap(int data[], int lastIndex) {    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {        //k保存正在判断的节点        int k = i;        //如果当前k节点的子节点存在        while (k * 2 + 1 <= lastIndex) {            //k节点的左子节点的索引            int biggerIndex = 2 * k + 1;            //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在            if (biggerIndex < lastIndex) {                //如果右子节点的值较大                if (data[biggerIndex] < data[biggerIndex + 1]) {                    //biggerIndex总是记录较大子节点的索引                    biggerIndex++;                }            }            //如果k节点的值小于其较大的子节点的值            if (data[k] < data[biggerIndex]) {                //交换他们                swap(data, k, biggerIndex);                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值                k = biggerIndex;            } else {                break;            }        }    }}

8.基数排序

用于大量数，很长的数进行排序时。

将所有的数的个位数取出，按照个位数进行排序，构成一个序列。

将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。

public void baseSort(int a[]) {    //首先确定排序的趟数;    int max = a[0];    for (int i = 1; i < a.length; i++) {        if (a[i] > max) {            max = a[i];        }    }    int time = 0;    while (max > 0) {        max /= 10;        time++;    }    //创建是个队列    List
    
     
      > queue = new ArrayList
      
       
        >();    for (int i = 0; i < 10; i++) {        ArrayList
        
          queue1 = new ArrayList<>();        queue.add(queue1);    }    //进行time次分配和收集;    for (int i = 0; i < time; i++) {        //分配数组元素;        for (int j = 0; j < a.length; j++) {            //得到数字的第time+1位数;            int x = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);            ArrayList
         
           queue2 = queue.get(x); queue2.add(a[j]); queue.set(x, queue2); } int count = 0;//元素计数器; //收集队列元素; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList
          
            queue3 = queue.get(k); a[count] = queue3.get(0); queue3.remove(0); count++; } } }}