排序算法

排序算法

冒泡排序法

选择排序法

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