java中几种常见的排序算法总结

目录

• 本节目标；
• 【插入排序】
• 【优化版】
• 【希尔排序】
• 【选择排序】
• 【堆排序】 
• 【冒泡排序】
• 介绍一个冒泡排序的优化方法； 
• 【快速排序】
• 【归并排序】
• 【正文】
• 【代码简介；】 
• 【排序总结】

本节目标；

：分析常见的比较排序算法基本原理及实现

：分析排序算法的性能分析

：分析Java中常用排序方法

1 排序

排序，就是使一串记录，按照其中某个或某些关键字的大小，递增或递减排列的操作。

平时的上下文中，提到排序 通常指排升序。

2 稳定性

两个相同的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则称该算法具备稳定发行。

【插入排序】

【优化版】

分析步骤；

第一步；将第一个元素下标设置为 i ，设 index  与 i 指向同一个元素

第二部 设置循环 利用 j  循环找出除 第一个元素以为最小的元素 将其交到index下

第三步 将index 与 第一个元素交换

 public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;  只要j回退的时候，遇到了 比tmp小的元素就结束这次的比较
                    break;
                }
            }
            //j回退到了 小于0 的地方
            array[j+1] = tmp;
        }
    }

【希尔排序】

(以了解为主 面试很少考的）

【分析步骤 】

【选择排序】

分析步骤；

第一步；将第一个元素下标设置为 i ，设 index  与 i 指向同一个元素

第二部 设置循环 利用 j  循环找出除 第一个元素以为最小的元素 将其交到index下

第三步 将index 与 第一个元素交换

【堆排序】 

注释 ！其基本原理还是排序.只其用堆来进行无序间排序，不用遍历进行排序

 public static void createHeap(int[] array) {
     for (int parent = (array.length - 1 - 1) / 2; parent > 0; parent--) {//设置出父亲节点
            shiftDown(array, parent, array.length);//
        }
    }
    public static void shiftDown(int[] array, int parent, int len) {
        int child = 2 * parent + 1;//设置出子节点
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;//以防有两个子节点 找出两个子节点最大一位
            }
            if (array[child] > array[parent]) {
            swap(array, parent, child);//交换父亲节点和子节点
            parent = child;//从新设置父亲节点
            child = 2*parent+1;
        }else{
            break;
        }
    }
    }
    public static void heapSort(int[] array) {//
        createHeap(  array);
        int end  = array.length-1;//每次交换完最后一位元素减一位
        while(end > 0){
            swap(array,0,end);
            shiftDown(array,0, array.length-1);//这个循环里 向下转型
            end--;
        }
    }

【冒泡排序】

注释；可能是几种排序比较简单的一种

介绍一个冒泡排序的优化方法； 

【快速排序】

原理简介-总览

1   从待排序区间选择一个数，作为基准值（pivot）

2   partition：遍历整个待排序区间， 将比基准小的(可以与基准相同)放在基左侧，将比基准大                   的(可以与基准相同）放在基准右侧。

3   采用分治思想，对左右两个小区间按照同样的方法进行处理  直到小区间的长度 == 1； 则其                 代表有序，如果长度 ==0， 则代表没有元素。

 public static void quick(int[] array,int left,int right) {
      if( left >= right) {//判断递归条件 不满足退出
          return;
      }
        int pivot =  partition( array,left,right);//找出基准值
        quick( array, left, pivot-1);//左侧进行递归
        quick( array, pivot+1 ,right);//右侧进行递归
    }
    private static int partition(int[] array,int start,int end) {
            int tmp = array[start];
            while(start< end){//
                while(start< end &&array[end] >  tmp){//末尾值比tmp大时 将末尾下标减减
                    end--;
                }
               array[start] = array[end];//在右侧遇到比tmp小的元素 进行交换
              while(start< end && array[start] < tmp ){//先从头部进行比较 比tmp小时交换
                  start++;
              }
              array[end] = array[start];
            }
            array[end] = tmp;
            return end;
    }
    public static void quickSort(int[] array) {
       quick(array,0, array.length-1);
        }
}
}

【归并排序】

原理-总览

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法采用分治法（Divide and Conquer)的一个非常典型的应用。将以有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

在此之前先复习一下(链表题）【合并两个有序链表】（归并排序的基础）

public static int[] mergeArray(int[] array1,int[] array2) {
        //注意判断参数
        int [] tmp = new int[array1.length + array2.length];
        int i = 0;
        int s1 = 0;
        int e1 = array1.length-1;
        int s2 = 0;
        int e2 = array2.length-1;
        while( s1<e1 && s2<e2){
            if(array1[s1] < array2[s2]){
                tmp[i++] = array1[s1++];

            }
            if(array1[s1] > array2[s2]){
                tmp[i++] = array2[s2++];
            }
        }
       while( s1<= e1){
           tmp[i++] = array1[s1++];
       }
       while( s2<= e2){
           tmp[i++] = array2[s2++];
       }
        return tmp;

【正文】

【代码简介；】 

 public static void mergeSort1(int[] array) {

 mergeSortInternal(array,0,array.length-1) ;

}
private static void mergeSortInternal(int[] array,int low,int high) {
           if(low > high){
           return ;
           }
   int mid  = (low +(high-low))/2;//找到数组的中间位置 分为左右两部分
    mergeSortInternal( array, low,mid-1 );// 将左边部分进行递归排序
   mergeSortInternal( array, mid+1,high );// 将右边部分进行递归排序
    merge(array,low,mid,high);// 将两部分进行合并

}
private static void merge(int[] array,int low,int mid,int high) {
         int [] tmp = new int[array.length];//创建一个新的数组
             int s1 = low;
             int e1 = mid;
             int s2 = mid+1;
             int e2 = high;
             int i = 0;
     while(s1<e1 && s2<e2){//循环的的条件
       if(array[s1] < array[s2]){
          tmp[i++] =  array[s1++];
         }else{
           tmp[i++] = array[s2++];
          }

      }
       while(s1 < s2){//当到这一步 说明左侧比右侧长   将左侧剩余部分衔接到数组中
         tmp[i++] = array[s1++];
     }
      while(s2 < e2){
         tmp[i++] =  array[s2++];//当到这一步 说明左侧比右侧长   将左侧剩余部分衔接到数组中

}
for(int j = 0; j < i; j++){//将tmp数组中元素放置array数组中
     array[i+low] = tmp[j];

}

【排序总结】

到此这篇关于java中几种常见的排序算法总结的文章就介绍到这了,更多相关java排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！