冒泡排序和快速排序实现原理

面试经常遇到这个问题,所以整理下,以便理解。

经常用到的排序方法有两种,冒泡排序和快速排序。

1.先说快速排序

原理:每一次比较相邻两个数的大小,通过第一轮循环排序,找到最大值放到后面,第二轮找到二大值放后面。

代码实现:

 sort(arr: Array<any>) {
        for(let i = 0; i<arr.length;i++) {
            for(let j = 0;j<arr.length-i-1;j++){
                let tmp = arr[j];
                if(arr[j] > arr[j+1]){
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }

2.冒泡排序

原理:取一个中间值,通过这个之间值和数组中的树相比,比它小的放左边,比它大的放右边,再依次递归左侧和右侧的数组,以此达到排序目的。

代码实现:

 quickSort(arr:Array<any>):Array<any> {
        if( arr.length < 1) {
            return  arr;
        }
        let num = Math.floor(arr.length/2);
        let middle = arr.splice(num,1)[0];
        let leftArr = [];
        let rightArr = [];
        for(let i = 0;i < arr.length; i++) {
            if (middle > arr[i]) {
                leftArr.push(arr[i]);
            } else {
                rightArr.push(arr[i]);
            }
        }
        return this.quickSort(leftArr).concat([middle],this.quickSort(rightArr));
    }

 

上一篇:牛客剑指Offer——旋转数组的最小数字


下一篇:笔记:Python实现二分查找