排序算法学习小结

排序算法小结

• 冒泡排序：它是一种简单的排序算法，通过重复地走访要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端，就像气泡上升一样，其时间复杂度为O(n²)，是稳定的排序算法。

• 插入排序：插入排序的工作原理是对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就像打扑克牌时，每次拿到一张新牌，都会将其插入到手中已有的有序牌中的合适位置，时间复杂度为O(n²)，是稳定的排序算法。

• 选择排序：选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕，时间复杂度为，是不稳定的排序算法。

• 快速排序：快速排序采用分治策略，先从数列中挑出一个元素作为基准值，将数列中比基准值小的元素都移到基准的左边，比基准值大的元素都移到基准的右边，然后对左右两个子数列分别重复上述操作，直到每个子数列只有一个元素，此时整个数列就有序了。平均时间复杂度为O(n log n)，但最坏情况会退化为O(n²)，是不稳定的排序算法。

• 归并排序：归并排序是把待排序的序列分成若干个长度为 1 的子序列，然后将这些子序列两两合并，得到若干个长度为 2 的有序子序列，再将这些长度为 2 的子序列两两合并，得到若干个长度为 4 的有序子序列，以此类推，直到最终合并成一个长度为 n 的有序序列。其时间复杂度始终为O(n log n)，是稳定的排序算法，但需要额外的空间来进行合并操作，空间复杂度为O(n)。

稳定性：相等元素的相对顺序是否保持不变，比如说数组中有5个5，这5个5的相对顺序不会发生改变。

冒泡排序

在一开始打比赛的时候不会用语言自带的sort排序,自己直接手敲了个冒泡排序:(。

第一层for循环是对第二层for循环的次数,第二层for循环是从数组的开始到结束，进行两两比较大小，大的放在后面，第二层循环之后，一定可以找到最大的数，并且最大的数在数组的尾部。

public static int[] bubbleSort(int[] arr, int size) {
        for (int i = 0; i < size-1; i++) {//下面j的循环次数
            for (int j = 0; j < size-i-1; j++) {
                if (arr[j] > arr[j+1]) {//前面大，则进行交换
                    arr[j] = arr[j]^arr[j+1];
                    arr[j+1] = arr[j]^arr[j+1];
                    arr[j] = arr[j]^arr[j+1];
                }
            }
        }
        return arr;
    }

插入排序

插入排序，排序的逻辑和名字相同，插入已经排序好的数组，首先，把排序好的数组的值最右边+1的值赋给temp，这个temp现在属于未排序的，然后while 循环从右到左遍历已经排序好的数组，当temp的值小于比较的值时，比较的值向右移动一位，temp值向左，直到遇见大于的值，大于的值直接插入。下面i!=j是进行赋值的，当i=j时就刚好temp值比排序好的数组最大值还要大。

public static int[] insertionSort(int[] arr,int size) {
        int temp;
        for (int i = 1; i < size ; i++) {
            temp = arr[i];
            int j = i;
            while ( j > 0 && arr[j-1] > temp) {
                arr[j]= arr[j-1];
                j--;
            }
            if (i!=j){
                arr[j] = temp;
            }
        }
        return arr;
    }

选择排序

感觉和冒泡差不多，每次选择最小值，把最小值和i所在的值进行交换。

for (int i = 0; i <size-1 ; i++) {
            int min =i;
            for (int j = i+1; j < size; j++) {
                if (arr[j] < arr[min]) {
                    min=j;
                }
            }
            if (min != i) {
                arr[min] = arr[min]^arr[i];
                arr[i] = arr[min]^arr[i];
                arr[min] = arr[min]^arr[i];
            }
        }

快速排序

快速排序，找基准值，把比基准值小的数放在基准值的左边，比基准值大的数放在右边， 下面代码，由i，j两个指针去走，如果找到arr[i]比基准值大，停，如果找到arr[j]比基准值大,停，交换arr[i]和arr[j]的值, 大致分为两边，左边是比基准值小的，右边是大的，最后把基准值和arr[i]进行交换,arr[i]一定是小于等于基准值的，这时基准值就在中间了， 而左边也是小于基准值的，右边也是大于基准值的。 快速一轮找到基准值小的，和基准值大的，再分成两个组开始下去找，直到左等于右

static void quickSort(int[] arr, int left, int right) {
        if(left >= right){
            return ;
        }
        int partitionIndex  = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex+1, right);
        return ;
    }
    static int partition(int[] arr, int left, int right) {
        int i =left;
        int j =right;
        while(i<j){
            while(i<j && arr[j] >= arr[left])
                j--;
            while (i<j && arr[i] <= arr[left])
                i++;
            swap(arr, i, j);
        }
        swap(arr, i,left);
        return i;
    }
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

归并排序

归并往下递归直到左等于右，左等于右返回，两个数比较，合并，再返回，四个数比较，合并，返回，依次类推最后完成排序，和快排不同的是，它是先探索到底，然后，逐级比较合并返回到上面。快速则一开始就分左右，探到底则完成排序。

static void mergeSort(int left, int right) {
        if(left >= right){
            return;
        }
        int mid = left + (right - left)/2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }
​
    //合并
    static void merge(int left, int mid, int right) {
        //确保三个值不要变
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
            }
        }
​
        //i没走完，把i剩余的数放入临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
​
        //j没走完，把j剩余的数放入临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }
​
        //将数组一一替换成已经排序好的临时数组
        for (k=0;k<temp.length;k++) {
            arr[left+k] = temp[k];
        }
    }