排序算法Python、Java实现

自己的学习笔记，如有错误，望大家批评指正！！！

1.概念理解

image.png

2.排序算法

image.png

3.十大排序算法的时间复杂度、空间复杂度、稳定性对比

排序算法对比.png

4.排序算详解

4.1 冒泡排序(Bubble Sort)

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

4.1.1 算法描述

image.png

4.1.2 代码实现

• Python代码

"""冒泡排序"""
def bubbleSort(arr):
    length = len(arr)
    for i in range(length):
        for j in range(i, length):
            if arr[i] > arr[j]:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp

• Java代码

 /**
     * 冒泡排序
     * */
    public static void bubbleSort(int[] arr){
        int len = arr.length;
        for (int i = 0;i < len;i++){
            for (int j = i;j < len;j++){
                if (arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

4.2 快速排序(Quick Sort)

  快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

4.2.1 算法描述

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
• 相比冒泡排序，每次交换是跳跃式的

4.2.2 代码实现

• Python代码

"""快速排序"""
def QuickSort(arr, left, right):
    # 递归退出的条件
    if left >= right:
        return
    # 设定起始的基准元素
    key = arr[left]
    # l为序列左边在开始位置的由左向右移动的游标
    l = left
    # r为序列右边末尾位置的由右向左移动的游标
    r = right
    while l < r:
        # 如果l与r未重合，r(右边)指向的元素大于等于基准元素，则r向左移动
        while arr[r] >= key and l < r:
            r -= 1
        # 走到此位置时r指向一个比基准元素小的元素,将r指向的元素放到l的位置上,此时r指向的位置空着,接下来移动l找到符合条件的元素放在此处
        arr[l] = arr[r]
        # 如果l与r未重合，l(右边)指向的元素小于等于基准元素，则l向右移动
        while arr[l] <= key and l < r:
            l += 1
        # 此时l指向一个比基准元素大的元素,将l指向的元素放到r空着的位置上,此时l指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
        arr[r] = arr[l]
    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
    # 将基准元素放到该位置,
    arr[l] = key
    # 对基准元素左边的子序列进行快速排序
    QuickSort(arr, left, l-1)
    # 对基准元素右边的子序列进行快速排序
    QuickSort(arr, l+1, right)

• Java代码

/**
     * 快速排序
     * 分治法
     * */
    public static void QuickSort(int[] arr,int left,int right){
        // 判断终止条件 递归退出的条件
        if (arr == null || arr.length == 0){
            return;
        }
        if(left > right){
            return ;
        }
        // 设定起始的基准元素
        int key = arr[left];
        // l为序列左边在开始位置的由左向右移动的游标
        int l = left;
        //  r为序列右边末尾位置的由右向左移动的游标
        int r = right;
        while (l < r){
            //如果l与r未重合，r(右边)指向的元素大于等于基准元素，则r向左移动
            while (arr[r] >= key && l < r){
                r--;
            }
            // 走到此位置时r指向一个比基准元素小的元素,将r指向的元素放到l的位置上,此时r指向的位置空着,接下来移动l找到符合条件的元素放在此处
            arr[l] = arr[r];
            // 如果l与r未重合，l(右边)指向的元素小于等于基准元素，则l向右移动
            while (arr[l] <= key && l < r){
                l++;
            }
            // 此时l指向一个比基准元素大的元素,将l指向的元素放到r空着的位置上,此时l指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
            arr[r] = arr[l];
        }
        //退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
        //  将基准元素放到该位置,
        arr[l] = key;
        // 对基准元素左边的子序列进行快速排序
        QuickSort(arr, left, l-1);
        // 对基准元素右边的子序列进行快速排序
        QuickSort(arr, l+1, right);
    }

4.3 简单插入排序(Insertion-Sort)

插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4.3.1 算法描述

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

4.3.2 代码实现

• Python代码

"""插入排序"""
def InsertionSort(arr):
    length = len(arr)
    for i in range(length):
        for j in range(i,0,-1):
            if arr[j] < arr[j-1]:
                temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp

• Java代码

 /**
     * 插入排序
     * */
    public static void InsertionSort(int[] arr){
        int len = arr.length;
        for (int i = 1;i < len;i++){
            for(int j = i;j > 0;j--){
                if (arr[j] < arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }

4.4 希尔排序(Shell Sort)

第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.4.1 算法描述

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.4.2 代码实现

• Python代码

"""希尔排序"""
def ShellSort(arr):
    length = len(arr)
    # 1. 设置步长
    step = length // 2
    while step > 0:
        for i in range(step,length):
            temp = arr[i]
            j = i
            while j >= step and arr[j-step] > temp:
                arr[j] = arr[j-step]
                j -= step
            print(i)
            print(temp)
            arr[j] = arr[i]
        step //= 2

• Java代码

 /**
     *希尔排序
     * 是简单插入排序的改进版,它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
     */
    public static void ShellSort(int[] arr){
        int len = arr.length;
        int step = len / 2;
        while (step > 0){
            for(int i = step;i < len;i++){
                int temp = arr[i];
                int j = i;
                while (j >= step && arr[j-step] > temp){
                    arr[j] = arr[j-step];
                    j -= step;
                }
                arr[j] = temp;
            }
            step /= 2;
        }
    }

4.5 选择排序(Selection-sort)

 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

4.5.1 算法描述

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)- 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

4.5.2 代码实现

• Python代码

"""选择排序"""
def SelectionSort(arr):
    length = len(arr)
    for i in range(length-1):
        temp = arr[i]
        minIndex = i
        for j in range(i+1, length):
            if arr[j] < arr[minIndex]:
                minIndex = j
        arr[i] = arr[minIndex]
        arr[minIndex] = temp

• Java代码

/**
     * 选择排序
     * 先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
     * 然后，再从剩余未排序元素中继续寻找最小（大）元素，
     * 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     * */
    public static void SelectionSort(int[] arr){
        int len = arr.length;
        for(int i = 0;i < len;i++){
            int temp = arr[i];
            int minIndex = i;
            for (int j = i+1;j < len;j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

4.6堆排序(Heap-Sort)

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

4.6.1 算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

4.6.2 代码实现

• Python代码

"""堆排序"""
# 二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k + 1和 2k+2
def heapsort(array):
    # 遍历非叶子节点，建立堆结构数组
    length = len(array)
    for i in range(length-1, -1, -1):
        adjustHeap(array, i, length)
        print("arr of heap:", array)
    # 堆积树建立完成，开始排序
    for j in range(length-1, 0 ,-1):
        array[0], array[j] = array[j], array[0]
        print(array)
        adjustHeap(array, 0, j)
# 维护堆的性质
def adjustHeap(array, i, length):
    # 对第i号进行堆调整，获取非叶子节点数据
    temp = array[i]
    # 非叶子节点的左子节点
    k = 2 * i + 1
    # 遍历对比k后面的节点，把temp放入合理的位置
    while k < length:
        # k+1 < length 确保有左右节点才比较
        if k + 1 < length and array[k] < array[k+1]:
            # 如果左子节点比右子节点小，k就切换到右子节点
            k += 1
        # 如果子节点有更大的
        if array[k] > temp:
            # 父节点替换为更大的
            array[i] = array[k]
            # 记录当前最大点位置
            i = k
        else:
            # 因为堆的特点，后面的更不满足
            break
        # k 切换到下一个左子节点
        k = 2 * k + 1
    # 此时i是空位，i上层的都比temp大，temp放到这里
    array[i] = temp

• Java代码

 /**
     * 堆排序
     * # 二叉树很容易就存储在数组中。
     * 位置 k 的节点的父节点位置为 k/2，
     * 而它的两个子节点的位置分别为 2k + 1和 2k+2
     * */
    public static void heapSort(int[] arr){
        //遍历非叶子节点，建立堆结构数组
        int len = arr.length;
        for (int i = (len-1);i > -1;i--){
            adjustHeap(arr, i, len);
        }
        // 堆积树建立完成，开始排序
        for (int j = (len-1);j > 0;j--){
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            adjustHeap(arr,0, j);
        }
    }
    // 维护堆的性质:完全二叉树，子节点的值要小于父节点的值
    public static void adjustHeap(int[] arr, int i,int len){
        //对第i号进行堆调整，获取非叶子节点数据
        int temp = arr[i];
        // 非叶子节点的左子节点
        int k = 2 * i + 1;
        // 遍历对比k后面的节点，把temp放入合理的位置
        while (k < len){
            // k+1 < length 确保有左右节点才比较
            if (k + 1 < len && arr[k] < arr[k+1]){
                // 如果左子节点比右子节点小，k就切换到右子节点
                k += 1;
            }
            // 如果子节点有更大的
            if (arr[k] > temp){
                // 父节点替换为更大的
                arr[i] = arr[k];
                // 记录当前最大点位置
                i = k;
            }else {
                // 因为堆的特点，后面的更不满足
                break;
            }
            // k 切换到下一个左子节点
            k = 2 * k + 1;
        }
        // 此时i是空位，i上层的都比temp大，temp放到这里
        arr[i] = temp;
    }

4.7归并排序(Merge-Sort)

   归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

4.7.1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

4.7.2 代码实现

• Python代码

"""归并排序"""
def mergeSort(array):
    length = len(array)
    if length <= 1:
        return array
    mid = length // 2
    left = array[:mid]
    right = array[mid:]
    return merge(mergeSort(left),mergeSort(right))
# 合并两个有序的数组
def merge(left, right):
    array = []
    length_left = len(left)
    length_rigth = len(right)
    l = r = 0
    while  length_left > l and length_rigth > r:
        if left[l] <= right[r]:
            array.append(left[l])
            l += 1
        else:
            array.append(right[r])
            r += 1
    # 谁还有剩余就把谁全部放进去
    if l == length_left:
        for i in right[r:]:
            array.append(i)
    else:
        for i in left[l:]:
            array.append(i)
    return array

• Java代码

/**
     * 归并排序
     * 采用分治法,将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
     *
     * @return*/
    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }
    private static void mergeSort(int[] arr,int left,int right,int []temp){
         if (left < right){
             int mid = (left+right) / 2;
             mergeSort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
             mergeSort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
             merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
         }
    }
    // 合并两个有序的数组
    public static  void merge(int[] arr,int left,int mid,int right,int []temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right){
            if (arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid){
            temp[t++] = arr[i++];
        }
        while (j <= right){
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }

4.8 计数排序(Counting-Sort)

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

4.8.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

4.8.2 代码实现

• Python代码

"""计数排序"""
def counting_sort(array):
    # 找出数列中最大值和最小值 创建min-max这么多个0用来统计数列中每个值出现的次数，再从最小值依次排放到最大值
    # 找到最大值
    max_num = max(array)
    # 找到最小值
    min_num = min(array)
    # 负数数列
    neg_list = []
    # 非负数数列
    pos_list = []
    # 对负数和非负数分别处理
    for num in array:
        if num < 0:
            neg_list.append(num)
        elif num >= 0:
            pos_list.append(num)
    length_neg_list = len(neg_list)
    length_pos_list = len(pos_list)
    # 对负数数列进行处理
    if length_neg_list != 0:
        # 创建从最最小值到0来累计每个负数出现的次数
        neg_count_list = [0 for _ in range(min_num, 0)]
        length_neg_count_list = len(neg_count_list)
        # 对于负数列中的每个值+1操作
        for i in range(length_neg_list):
            neg_count_list[neg_list[i]] += 1
        #初始化排序索引为0
        neg_index = 0
        # 对于计数列表中的每一项
        for i in range(-length_neg_count_list,0):
            # 不为0表明有计数
            while neg_count_list[i] > 0:
                # 依次排放数值
                neg_list[neg_index] = i
                # 每次排放后索引加1
                neg_index += 1
                # 每次排放后对应的计数减1
                neg_count_list[i] -= 1
    if length_pos_list != 0:
        # 创建从0到最大值到来累计每个正数出现的次数
        pos_count_list = [0 for _ in range(0, max_num+1)]
        length_pos_count_list = len(pos_count_list)
        # 对于负数列中的每个值+1操作
        for i in range(length_pos_list):
            pos_count_list[pos_list[i]] += 1
        # 初始化排序索引为0
        pos_index = 0
        # 对于计数列表中的每一项
        for i in range(length_pos_count_list):
            # 不为0表明有计数
            while pos_count_list[i] > 0:
                # 依次排放数值
                pos_list[pos_index] = i
                # 每次排放后索引加1
                pos_index += 1
                # 每次排放后对应的计数减1
                pos_count_list[i] -= 1
    result_list = neg_list + pos_list
    return result_list

• Java代码

/**
     * 计数排序
     * */
    public  static int[] countingSort(int[] arr){
        int arr_len = arr.length;
        //1.取数组中的最大值和最小值
        int max_num = arr[0], min_num = arr[0];
        for (int i = 0;i < arr_len;i++){
            if (arr[i] > max_num){
                max_num = arr[i];
            }
            if (arr[i] < min_num){
                min_num = arr[i];
            }
        }
        // 2. 确定中间数组的长度
        int[] new_arr = new int[max_num - min_num + 1];
        //3. 统计原数组中值对应到新数组中值出现的次数
        for (int i = 0;i < arr_len;i++){
            new_arr[arr[i] - min_num] += 1;
        }
        //4. 创建返回的有序数组
        int[] res = new int[arr_len];
        //记录数组下标
        int index = 0;
        //5. 获取排序后的数组
        for (int i = 0; i < new_arr.length; i++){
            for (int j = 0;j < new_arr[i];j++){
                res[index++] = i + min_num;
            }
        }
        return res;
    }

4.9桶排序(Bucket-Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

4.9.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

4.9.2 代码实现

"""桶排序"""
"""
计数排序的改进版
找出数列中最大值和最小值 创建min-max这么多个桶用来统计数列中每个值出现的次数，再从第一个桶倾倒到最后一个桶
"""
def bucket_sort(array):
    length_array = len(array)
    # 找到最大值
    max_num = max(array)
    # 找到最小值
    min_num = min(array)
    bucket_list = [0 for _ in range(max_num-min_num+1)]
    length_bucket_list = len(bucket_list)
    # 添加值到对应的桶内，对应桶计数+1
    for i in range(length_array):
        bucket_list[array[i] - min_num] += 1
    # 结果列表
    print(bucket_list)
    result_list = []
    for i in range(length_bucket_list):
        print(i)
        if bucket_list[i] != 0:
            result_list += [i+min_num] * bucket_list[i]
    return result_list

4.10 基数排序(Radix-Sort)

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

4.10.1 算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

4.10.2 代码实现

"""基数排序"""
"""
比较位数上的值
比较每一位上的数字大小，当每一位比较完成排序也就完成
"""
def radix_sort(array):
    # 找到最大值
    max_num = max(array)
    # 找到最小值
    min_num = min(array)
    # 负数数列
    neg_list = []
    # 非负数数列
    pos_list = []
    # 对负数和非负数分别处理
    for num in array:
        if num < 0:
            neg_list.append(num)
        elif num >= 0:
            pos_list.append(num)
    length_neg_list = len(neg_list)
    length_pos_list = len(pos_list)
    # 负数进行排序
    if length_neg_list != 0:
        neg_num_digit = 0
        while neg_num_digit < len(str(min_num)):
            # 初始化数值列表
            neg_values_lists = [[] for _ in range(10)]
            # 对于数列中的每个数
            for neg_num in neg_list:
                neg_values_lists[int(neg_num/(10**neg_num_digit)) % 10].append(neg_num)
            print(neg_values_lists)
            neg_list.clear()
            for neg_value_list in neg_values_lists:
                for neg_num in neg_value_list:
                    neg_list.append(neg_num)
            # 比较下一位
            neg_num_digit += 1
    # 正数进行排序
    if length_pos_list != 0:
        pos_num_digit = 0
        while pos_num_digit < len(str(max_num)):
            # 初始化数值列表
            pos_values_lists = [[] for _ in range(10)]
            # 对于数列中的每个数
            for pos_num in pos_list:
                pos_values_lists[int(pos_num / (10 ** pos_num_digit)) % 10].append(pos_num)
            pos_list.clear()
            for pos_value_list in pos_values_lists:
                for pos_num in pos_value_list:
                    pos_list.append(pos_num)
            # 比较下一位
            pos_num_digit += 1
    result_list = neg_list + pos_list
    return  result_list