一 概述

基本排序算法有如下：冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序，还有比较特殊的桶排序。

其中稳定性：两个相同的元素排序前后相对位置不变。

 

二 交换类排序 

 交换类 排序也就是冒泡排序和快速排序，冒泡：它是一种较简单的排序算法。遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！优化方式是如果一轮下来没有发生交换，则说明已经排序。

快速排序的思想中：选择一个基准元素，把小于它的全都移动到左边，大于的全部移动到右边。所以基准元素的位置确定了，然后递归进行左边数组和右边数组的定位操作。是一种分治的思想。

它的两个改进方法是：1.选择基准元素的时候，如果一直是最左边或是最右边元素，而恰好此时给定的元素相对有序，那么排序的递归将偏向一边，和搜索二叉树退化成链表的样子很像。所以增加随机性，随机选取基准元素。  2. 如果数组中存在大量的相同元素，一次扫描其实可以完成多个元素的定位 增加速度。

 

 

三 具体 实现代码

package sort;import java.util.Arrays;// 此类为交换类排序算法  包括冒泡排序 和快速排序// 冒泡排序的一个小优化 如果内层循环没有交换 则当前数组已经有序 可以跳出循环//快速排序有两个优化点，一是增加基准元素随机性 二是如果相同元素 比价多 一次可以定位多个元素public class JiaoHuan {    public static void main(String[] args) {        int arr[] = {1, -1, 10,10,10, -63,98, 86, 222};        quickSort1(arr, 0, arr.length - 1);        System.out.println(Arrays.toString(arr));    }    public static void maoPao(int arr[]) {        if(arr==null||arr.length==0)            return;        boolean flag = false;        for (int i = 0; i < arr.length; i++) {            flag = false;            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {                    flag = true;                    swap(arr, j, j + 1);                }            }            if(!flag){                break;            }        }    }    public static void quickSort(int arr[],int l,int r){        if (arr == null || arr.length == 0) {            return;        }        int q = partition(arr, l, r);        if(q>l){            quickSort(arr, l, q - 1);        }        if(q
     
      l){            quickSort(arr, l, brr[0] - 1);        }        if(brr[1]
      
       arr[r]) {               swap(arr, --m, l);           }           else{               l++;           }        }        swap(arr, r, m);        return new int []{k,m+1};    }  // 工具方法  实现两个数组元素的交换    public static void swap(int arr[], int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }}