算法-java排序实现总结

摘要：一常见的排序算法及时间复杂度二各排序算法的理解及实现冒泡排序算法描述比较相邻元素，如果第一个比第二个大，交换位置，这样每经过一趟就冒出一个最大的动图演示代码实现快速排序算法描述从数列中挑出一个元素，称为基准从左向右找比这个第一个比这个基

（1）算法描述

比较相邻元素，如果第一个比第二个大，交换位置，这样每经过一趟就冒出一个最大的

（2）动图演示

（3）代码实现

 public static int[] bubbleSort(int arr[]){
        int len = arr.length;
       for(int i = 0;iarr[j+1]){
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }
       return arr;
    }

（1）算法描述

从数列中挑出一个元素，称为"基准"（pivot）

从左向右找比这个第一个比这个基准大的数，从右往左找第一个比这个基准小的数，找到后互换位置

继续在此基础上执行第二步，直到两个寻找指针相遇

递归的（recursive）把小于基准值的序列和大于基准值的序列排序

（2）动图演示

 public static void quickSort(int[]arr, int left,int right) {
        if(left>right){return; }//递归的出口
        int i = left,j = right;
        int pivot = arr[left];//找到基准
        while (i < j) {
            //从右向左找第一个比基准值小的数
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            //从左向右找第一个比基准值大的数
            while (i < j && arr[i] <= pivot) {
                i++;
            }

            //两面都找到后互换位置
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        //left=right时于基准值互换
        int tmp = arr[j];
        arr[j] = arr[left];
        arr[left] = tmp;
        //分别递归的调用基准值的左边和右边
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);

    }

（1）算法描述

从第二个元素开始（因为认为第一个元素已经有序）向前扫描

如果前一个数小于当前元素，继续跳到下一个元素开始向前扫描

如果前一个数大于当前元素，继续向前扫描，直到找到小于这个数的元素，插到它的后面

（2）动图演示

（3）代码实现

  public static void insertSort(int[] array){
        int len = array.length;
        for(int i = 1;i0 && array[j-1]>temp;j--){
                //如果比待插入数大 ，向右移
                array[j] = array[j-1];
            }
            //如果比带插入数小，插在该数后面
            array[j] = temp;
        }

（1）算法描述

其实就是对插入排序进行了优化，先对相同间隔的一组数进行插入排序，使序列基本有序，再进行间隔为1的插入排序时，减少工作量。（代码实现可对照插入排序，其实就是多了一组循环）

（2）动图演示

（3）代码实现

 public static void shellSort(int[] array){
        int len= array.length;
        int gap;//增量长度
        for(gap = len/2;gap>0;gap/=2){
            for(int i = gap;i gap && array[j - gap] > temp; j-=gap) {
                    //如果比待插入数大 ，向右移
                    array[j] = array[j - gap];
                }
                //如果比待插入数小，插在该数后面
                array[j] = temp;
            }
        }
    }

（1）算法描述

将序列划分为有序区和无序区（初始状态有序区为空）

遍历无序区，选出最小的元素，放到有序区

（2）动图演示

（3）代码实现

   public static int[] selectSort(int array[]){
        for(int i=0;i
6.堆排序
（1）算法描述