常见八大排序算法

今天我们带来数据结构中常见的8大排序算法。

一，冒泡排序

思路：1，从头到尾比较相邻的元素，2，重复第一步n-1次

代码实现：

public void BubbleSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        for (int i = 0; i < str.length; i++) {
            for (int j = 0; j < str.length-1-i; j++) {
                if(str[j]<str[j+1]){
                    swap(str,j,j+1);
                }
            }
        }
        System.out.println(Arrays.toString(str));
    }

swap是交换，

private void swap(int[] str,int i,int j){
        int tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }

代码优化： 优化也不会优化到多好基本还是O(n方的复杂度)

 public void BubbleSortLevel(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        for (int i = 0; i < str.length; i++) {
            boolean a = false;
            for (int j = 0; j < str.length-1-i; j++) {
                if(str[j]<str[j+1]){
                    swap(str,j,j+1);
                    a = true;
                }
            }
            if(!a){
                break;
            }
        }
        System.out.println(Arrays.toString(str));
    }

二，插入排序

思路； 1，定义两个下标i,j，tmp，i从1开始向后遍历，把初始的下标值赋给tmp 2，j每次从i前面开始向前遍历，比较j下标的元素和tmp的值。

代码实现：

public void InsertSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int j=0;
        int tmp=0;
        for (int i = 1; i < str.length; i++) {
            tmp = str[i];
            for (j = i-1; j >=0 ; j--) {
                if(str[j]<tmp){
                    str[j+1] = str[j];
                }
                else {
                    break;
                }
            }
            str[j+1] = tmp;
        }
        System.out.println(Arrays.toString(str));
    }

三，选择排序

思路： 1，定义两个下标i，j；i从左向右遍历：2，我们创建一个tmpIndex记录i下标的值，j每次都在i的左边，与tmpIndex的值进行比较，记录新的tmpIndex的值，与i下标交换，重复这个步骤。

代码实现：

public void ChooseSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int j= 0;
        int tmpIndex = 0;
        for (int i = 0; i < str.length; i++) {
            tmpIndex = i;
            for (j = i+1; j < str.length; j++) {
                if(str[j]<str[tmpIndex]){
                    tmpIndex = j;
                }
            }
            swap(str,i,tmpIndex);
        }
        System.out.println(Arrays.toString(str));
    }

四，希尔排序

思路： 希尔排序实际就是多次进行快速排序，但是我们每次是不同的几组数进行排序，我们初始一个gap，gap的取值不一，我们一数组长度/2来赋给gap,每次相邻为gap的元素进行插入排序，再对gap/2，直到gap为1，我们的思路是插入排序对越有序的数组排序越有序

代码实现： 

    public void ShellSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int gap = str.length/2;
        while (gap>=1){
            ShellSort__InsertSort(str,gap);
            gap/=2;
        }
        System.out.println(Arrays.toString(str));
    }
    private void ShellSort__InsertSort(int[] str,int gap){
        int tmp = 0;
        int j = 0;
        for (int i = gap; i < str.length; i++) {
            tmp = str[i];
            for (j = i-gap; j >= 0; j-=gap) {
                if(str[j]<tmp){
                    str[j+gap] =str[j];
                }
                else {
                    break;
                }
            }
            str[j+gap] = tmp;
        }
    }

五，堆排序

思路： 以升序为例，降序建小根堆，升序建大根堆，

1，建堆  2，栈顶元素与尾元素互换，再进行向下调整  3，直到重复步骤2直到0下标。

代码实现： 

public void HeapSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        CreateHeap(str);
        for (int i = str.length-1; i >=0 ; i--) {
            swap(str,i,0);
            ShiftDown(str,0,i);
        }
        System.out.println(Arrays.toString(str));
    }

    private void CreateHeap(int[] str){
        int c = str.length-1;
        int p = (c-1)/2;
        while (p>=0){
            ShiftDown(str,p,str.length);
            p--;
        }
        System.out.println(Arrays.toString(str));
    }

    private void ShiftDown(int[] str, int parent,int usdSize){
        int child = 2*parent+1;
        while (child<usdSize){
            if(child+1<usdSize && str[child]<str[child+1]){
                child++;
            }
            if(str[child]>str[parent]){
                swap(str,child,parent);
                parent = child;
                child = 2*parent+1;
            }
            else {
                break;
            }
        }
    }

六，快速排序

思路： 1，选择一个基准，定义两个下标，一个从右往左走（先走），一个从左往右走，右边遇到小于基准的与左边大于基准的交换，

2，找到基准，从基准左边和右边递归，重复1的过程。

代码实现（递归实现）：

public void QuickSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));
    }
    private void QuickSortChild(int[] str,int start,int end){
        if(start>end){
            return;
        }
        int left = start;
        int right = end;
        int part = partition(str,left,right);
        QuickSortChild(str,start,part-1);
        QuickSortChild(str,part+1,end);
    }
    private int partition(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }

代码优化（递归实现）：（三数取中法）

public void QuickSort2(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));
    }
    private void QuickSortChild2(int[] str,int start,int end){
        if(start>end){
            return;
        }
        int left = start;
        int right = end;
        int mid = middle(left,(left+right)/2,right);
        swap(str,start,mid);
        int part = partition(str,left,right);
        QuickSortChild(str,start,part-1);
        QuickSortChild(str,part+1,end);
    }
    private int partition2(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }
    private int middle(int left,int middle,int right){
        int[] arr = new int[]{left,middle,right};
        Arrays.sort(arr);
        return arr[1];
    }

 代码实现（非递归实现）：

public void QuickSort3(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild3(str,0,array.length-1);
        System.out.println(Arrays.toString(str));

    }
    private void QuickSortChild3(int[] str,int start,int end){
        Deque<Integer> stack = new ArrayDeque<>();
        int part = partition3(str,start,end);
        if (part+1<end){
            stack.push(end);
            stack.push(part+1);
        }
        if(part-1>start){
            stack.push(part-1);
            stack.push(start);
        }
        while (!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            part = partition3(str,start,end);
            if (part+1<end){
                stack.push(end);
                stack.push(part+1);
            }
            if(part-1>start){
                stack.push(part-1);
                stack.push(start);
            }
        }
    }

    private int partition3(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }

七，归并排序

思路： 1，我们把数据平均分为两个部分定义左中右三个下标，左边递归，右边递归，

2，当左下标大于等于右递下标归停止，我们使用合并数组的方法，把每层递归后有序的左右子树有序化

代码实现：

public void MergeSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        MergeSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));

    }

    private void MergeSortChild(int[] str,int left, int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        MergeSortChild(str,left,mid);
        MergeSortChild(str,mid+1,right);

        MergeSort__new(str,left,mid,right);
    }
    private void MergeSort__new(int[] str,int left,int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] arr = new int[right-left+1];
        int i=0;
        while (s1<=e1 && s2<=e2){
            if(str[s1]<=str[s2]){
                arr[i] = str[s1];
                i++;
                s1++;
            }
            if(str[s2]<str[s1]){
                arr[i] = str[s2];
                i++;
                s2++;
            }
        }
        while (s1<=e1){
            arr[i] = str[s1];
            i++;
            s1++;
        }
        while (s2<=e2){
            arr[i] = str[s2];
            i++;
            s2++;
        }

        for (int k = 0; k < i; k++) {
            str[k+left] = arr[k];
        }
    }

八，计数排序

计数排序适合排那些一定范围的大量数据，比如1-100的考试成绩

思路： 1，我们遍历原数组，找出最大值最小值，用他们的差值大小构建一个计数数组，

2，把原数组出现的数字-min放到计数数组里，有一个计数数组就加一，循环遍历计数数组，直到计数数组全部元素都为0

代码实现： 

public void CountIngSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int max = str[0];
        int min = str[0];
        for (int i = 0; i <str.length ; i++) {
            if(str[i]>max){
                max = str[i];
            }
            if(str[i]<min){
                min = str[i];
            }
        }
        int[] count = new int[max-min+1];

        for (int i = 0; i < str.length; i++) {
            int a = str[i];
            count[a-min]+=1;
        }
        int j = 0;
        int i = 0;
        while (i<count.length) {
            while (count[i]!=0){
                str[j] = i+min;
                j++;
                count[i]--;
            }
            i++;
        }
        System.out.println(Arrays.toString(str));
    }