首页 计算机科学 Java 算法

# 排序算法

# 冒泡排序法

# 选择排序法

思路： 选择一个元素作为最小元素（一般是第一个），然后将这个元素与数组其他元素进行比较，如果比它还小则将其最小元素赋值给它，比较完一轮后，将这个最小元素放入到新数组（排序好的数组）并从原数组剔除出去，如此反复操作 n 轮

** 时间复杂度:**O (n²)

代码：

java :

/**
     * 寻找最小元素
     * @param arr 数组
     * @return 最小元素索引
     */
    public static int findSmallest(int []arr){
        int smallest = arr[0];
        int smallest_index = 0 ;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < smallest){
                smallest = arr[i];
                smallest_index = i ;
            }
        }
        return smallest_index;
    }
    /**
     * 返回去除元素的新数组
     * @param arr 原数组
     * @param element_index 最小元素索引
     * @return 新数组
     */
    public static int[] removeElement(int arr[],int element_index){
        int []array = new int[arr.length - 1];
        for(int i = 0 ,j =0;i<arr.length;i++){
            if (i!=element_index){
                array[j++] = arr[i];
            }
        }
        return array;
    }
    /**
     * 选择排序算法
     * @param arr 原数组
     * @return 排序好的新数组
     */
    public static int [] chooseSort(int arr[]){
        int []newArr = new int[arr.length];
        int index = 0 ;
        int len = arr.length ;
        for (int i = 0; i < len; i++) {
            int smallest_index = findSmallest(arr);
            newArr[index++] = arr[smallest_index];
            arr = removeElement(arr,smallest_index);
        }
        return newArr;
    }
python :
# 寻找最小元素，并返回最小元素索引
def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
# 选择排序法
def choose_sort(arr):
    sort_list = []
    for i in range(len(arr)):
        smallest_index = find_smallest(arr)
        sort_list.append(arr.pop(smallest_index))
    return sort_list
# 快速排序法
** 思路:** 选择数组中的一个元素作为基准元素，然后将其他元素与其比较，如果小的放入左边一个数组，如果大的放入右边的数组，反复操作，直至子数组只有 0 个或者 1 个元素为止。
时间复杂度：O (nlogn)
python :
# 快速排序法
# 思路：选择数组中的一个元素作为基准元素，然后将其他元素与其比较，如果小的放入左边一个数组，如果大的放入右边的数组，反复操作，直至子数组只有 0 个或者 1 个元素为止
# 这种思路可以使用递归的方式来做，将数组只有 0 个或者 1 个元素作为递归终止条件，后面再做归纳 --- 选择基准元素和子数组递归。
# 快速排序法
def quick_sort(arr):
    # 如果数组长度小于 2，则直接返回数组
    if len(arr) < 2:
        return arr
    # 将数组第一个元素作为基准元素
    pivot = arr[0]
    # 生成小于等于基准元素的子数组
    less = [i for i in arr[1:] if i <= pivot]
    # 生成大于基准元素的子数组
    right = [i for i in arr[1:] if i > pivot]
    # 合并数组
    return quick_sort(less) + [pivot] + quick_sort(right)
print(quick_sort([2, 7, 7, 4, 1, 9, 5, 3, 6, 8]))
java:
/**
     * 快速排序法
     * @param arr 原数组
     * @return
     */
    public static int [] quickSort(int []arr){
        // 如果数组长度小于等于 1，直接返回 基准条件
        if (arr.length <= 1){
            return arr;
        }
        // 取第一个元素作为基准元素
        int privot = arr[0];
        // 获取比基准元素小和比基准元素大的数组
        ArrayList<Integer> less = new ArrayList<>();
        ArrayList<Integer> greater = new ArrayList<>();
        for (int i = 1; i < arr.length ; i++) {
            if (arr[i] >= privot) {
                greater.add(arr[i]);
            }else {
                less.add(arr[i]);
            }
        }
        // 递归上述行为，直至获取到两个数组排序好的数组
        int[] lessArr = quickSort(less.stream().mapToInt(Integer::valueOf).toArray());
        int[] greaterArr = quickSort(greater.stream().mapToInt(Integer::valueOf).toArray());
        int []array = new int[arr.length];
        // 将其复制到新数组中
        System.arraycopy(lessArr,0,array,0,lessArr.length);
        System.arraycopy(greaterArr,0,array,lessArr.length+1,greaterArr.length);
        array[lessArr.length] = privot ;
        return array ;
    }