【数据结构】数据结构之排序

接上篇，我们先来了解一下堆排序，堆排序了解完，给大家总结了一些基本常见的排序算法，希望对大家的学习有所帮助。

堆排序

如果是将堆排成一个升序的，那就建立大根堆

具体代码：

    public void heapSort() {
        int end = userSize -1;
        while(end > 0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

如果是将堆排成一个降序的，那就建立小根堆

例题：

一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
A: (11 5 7 2 3 17)
B: (11 5 7 2 17 3)
C: (17 11 7 2 3 5)
D: (17 11 7 5 3 2)
E: (17 7 11 3 5 2)
F: (17 7 11 3 2 5)

因为堆排序默认是大根堆，所以排序后结果为：17 11 7 2 3 5

下面我们就开始来复习排序算法

排序的理解

是一个序列对象按照某个关键字进行递增或递减的操作

（1）稳定性：如果a原本在b前面，并且a=b，排序之后a仍然在b的前面，说明这个是稳定的，反之，就不稳定。

（2）内部排序：数据元素全部放在内存中的排序。

（3）外部排序：数据元素太多不能同时放在内存中，所以把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

一个稳定的排序，可以变成不稳定的排序

一个不稳定的排序，不可以变成稳定的排序

（4）10种排序比较

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n^1.3)	O(n^1.3)	O(n^1.3)	O(1)	不稳定
堆排序	O(n*logn)	O(n*logn)	O(n*logn)	O(1)	不稳定
快速排序	O(n*logn)	O(n*logn)	O(n^2)	O(logn)~O(n)	不稳定
归并排序	O(n*logn)	O(n*logn)	O(n*logn)	O(n)	稳定
计数排序	O(MAX(n,范围))	O(MAX(n,范围))	O(MAX(n,范围))	O(范围)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定
桶排序	O(n)	O(n+k)	O(n^2)	O(n+k)	基于桶内比较稳定

直接插入排序

未排序的数据元素，在已经排好的有序序列中从后向前扫描，找到对应位置然后插入
在扫描的过程中，需要反复把已经排序的元素向后挪动，为准备新插入的元素提供空间

          直接插入排序
    时间复杂度：
最坏：O(n^2) 数据元素全部逆序时
最好：O(n) 数据元素全部有序时
    空间复杂度：O(1)
数据元素基本上有序时，使用效果最好

代码：

 public 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 {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

例题分析：

对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较 ( C ) 次？（采用从后往前比较）
A: 3 B: 4 C: 5 D:6

先给前面排序 15 23 38 54 60 72 96 45 83
45插入比较了5次

希尔排序（缩小增量算法）

希尔排序是选的一个增量值分组，然后对每组使用直接插入排序算法排序，随着增量值减小，每组包含的值也越来越多，当增量值减为1时，整个序列在一组内排序

     * 希尔排序
     * 时间复杂度：O(n^1.3 - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定

具体代码：

  private static void shell(int[] array,int gap) {
        for (int i  = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }

例题：

下列排序法中，最坏情况下时间复杂度最小的是（A）
A: 堆排序O(nlogn) B: 快速排序O(n2) C: 希尔排序 O(n^1.5) D: 冒泡排序 O(n^2)

直接选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

     * 直接选择排序     
     * 数据复杂度：O(n^2) （对数据不敏感，不管数据有序还是无序都是这样）
     * 空间复杂度：O(1)
     * 稳定性：不稳定

代码：

 public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //每次将i下标的值当做最小值
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                   minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    private static void swap(int[] array,int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

那么如果用两个一个minIndex去找最小值，一个maxIndex去找最大值，然后用left指向前，right指向后，比如说是升序那就minIndex和left交换， maxIndex和right交换，这样效率应该是比第一种方法要快

代码：

 public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length-1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,maxIndex);
            //修正maxIndex下标
            if(left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

     * 堆排序    
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定

具体代码：

  public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length-1;
        while(end >= 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    private static void createBigHeap(int[] array) {
        for (int parent= (array.length-1-1)/2; parent >= 0 ; parent--) {
           shiftDown(array,parent,array.length);
        }
    }
    //向下调整
    private 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,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

关于排序，下面说法不正确的是 (D)
A: 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B: 归并排序是一种稳定的排序,堆排序和快排均不稳定
C: 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D:归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
堆排序空间复杂度的为O(1)

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复的进行上面的步骤，直到没有再需要交换的

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

下列排序算法中稳定且时间复杂度为O(n2)的是     (B)
A: 快速排序    B: 冒泡排序     C: 直接选择排序     D: 归并排序

快速排序（无序使用最好）

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

     * 时间复杂度：
     *    最优：O(n*logn)  每次均分待排序数组
     *    最坏：O(n^2)  数组有序或逆序
     * 空间复杂度：最好：O(logN)
     *            最坏：O(N)   当n足够大时，递归的深度就大
     * 稳定性：不稳定

递归实现

Hoare法找基准

  public static void quickSort(int[] array) {
        quick(array,0, array.length-1);
    }
 
    private 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);
    }
    //找k
    private static int partition(int[] array,int start, int end) {
        int i = start;
        int key = array[start];
        while (start < end) {
            while (start < end && array[end] >= key) {
                end--;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }

挖坑法

 //挖坑法
    private static int partition2(int[] array,int start, int end) {
        int key = array[start];
 
        while(start < end) {
            while(start < end && array[end] >= key) {
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }

前后指针法

    private static int partition3(int[] array,int left, int right) {
        int prev = left ;
        int cur = left+1; 
        while (cur <= right) { 
            if(array[cur] < array[left] && array[++prev] != array[left]) { 
                swap(array,cur,prev); 
            }
            cur++;
        }
        swap(array,prev,left); return prev;
    }

三数取中找基准

 private static int midNumIndex(int[] array, int left, int right) {
        int mid = (left+right) / 2;
 
        if (array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

三数取中递归

  private static void quick1(int[] array,int left, int right) {
        //取= 是只有一个节点了 >有可能没有子树
        if (left >= right) {
            return;
        }
        int index = midNumIndex(array,left,right);
        //找到三数中，中间大小的数字，和第一个交换
        swap(array,left,right);
        //此时就按之前正常那个Hearo法执行就可以了
        int pivot = partition1(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

非递归实现

 public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot = partition2(array,left,right);
 
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
 
        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition1(array, left, right);
            //当左边或右边区间只剩一个元素时，不用给栈中放
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

1.快速排序算法是基于()的一个排序算法。（A）
A：分治法 B：贪心法 C：递归法 D：动态规划法
2.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（A）
A: 34，56，25，65，86，99，72，66
B: 25，34，56，65，99，86，72，66
C: 34，56，25，65，66，99，86，72
D: 34，56，25，65，99，86，72，66
用挖坑法得出选A

归并排序

**加粗样式归并排序是建立在归并操作上的一种有效的排序算法,将已有序的子序列合并，得到完全有序的序列；也就是先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 **

     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     * 归并排序

归并排序的非递归方法

 public static  void mergerSort2(int[] array) {
        int gap = 1;//每组的数据
        while(gap < array.length) {
            for (int i = 0; i < array.length; i += gap*2) {
                int s1 = i;
                int e1 = s1+gap-1;
                if(e1 >= array.length) {
                    e1 = array.length-1;
                }
                int s2 = e1+1;
                if(s2 >= array.length) {
                    s2 = array.length -1;
                }
                int e2 = s2+gap-1;
                if (e2 >= array.length) {
                    e2 = array.length-1;
                }
                merge(array,s1,e2,e1);
            }
            gap *= 2;
        }
    }

以下排序方式中占用O(n)辅助存储空间的是   (D)
A: 简单排序    B: 快速排序     C: 堆排序     D: 归并排序

计数排序（不比较）

计数排序通过计算数组中每个元素的出现次数来对数组的元素进行排序。将计数存储在辅助数组中，并通过将计数映射为辅助数组的索引来完成排序。

 public static void countSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if (array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //确定了最大 最小值
        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        //开始遍历array数组 进行计数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            count[val-minVal]++;
        }
        int index = 0;//array数组下标
        for (int i = 0; i < count.length; i++) {
            //确保当前count数组 可以检查完
            while(count[i] != 0) {
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

基数排序

基数排序是利用分配和收集两种基本操作。

基数排序是一种按记录关键字的各位值逐步进行排序的方法。

此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。

  private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数
        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }
        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];
 
            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }
            //更改buckets[i]，
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }
            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }
            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }
 
    }

桶排序

将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了

public static void bucketSort(int[] arr){
    // 计算最大值与最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    // 计算桶的数量
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    // 将桶中的元素赋值到原序列
	int index = 0;
	for(int i = 0; i < bucketArr.size(); i++){
		for(int j = 0; j < bucketArr.get(i).size(); j++){
			arr[index++] = bucketArr.get(i).get(j);
		}
	}  
}