内排序

冒泡排序

  • 决定冒泡的方向,每次冒泡相邻元素比较,每次固定一个泡。
  • 如果一趟未产生任何交换,则整个序列已排序,无需再比较。
  • 时间复杂度:比较的次数n-1 … 1 , 总和 O(n^2) , 空间复杂度 O(1)
int a[100] = {1, 2, 10, 3, 5, 4, 2};
void swap(int i, int j) {
    if (i != j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
//冒泡排序, 从小到大
void bubbleSort(int a[], int n) {
    if (n <= 1) {
        return;
    }

    for (int i = 0; i < n - 1; i++) { //每次要确定的冒泡元素
        int sorted = 1;  //做一个优化,如果一趟排序中都没有产生交换,则不需要以后操作
        for (int j = n - 1; j > i; j--) { //从后往前冒
            if (a[j] < a[j - 1]) {
                swap(j, j-1);
                sorted = 0;
            }
        }

        if (sorted == 1) {
            break;
        }
    }
}

快速排序

  • 快排核心找基准数,把基准数放到某一个位置,左边的都比它小,右边的都比它大。
  • 如果我们以最左边的为基准,那么需要注意的是为什么从右边找,因为从左边找,你可能无法找到比它小的元素,这样你就无法执行基准数和找到的数的交换,如果从右边找,至少可以找到刚好等于基准数的元素,这样才满足基准数左边都小于,右边都大于的思想。
  • 时间复杂度:如果每次被二分,总共被分成的是logn 趟, 每次比较的是 n 次, 时间复杂度 O(nlogn), 空间复杂度 O(1) 。
void quickSortByRange(int a[], int left, int right){
    if (left >= right) {
        return;
    }
    int l = left;
    int r = right;
    int pivotIndex = left;
    int pivot = a[left];
    //基准数在左边,为什么是从右边找,而不是从左边找呢,因为如果从左边找,你很可能找不到,这样就无法执行
    //基准数和相遇点的交换了,而从左边找,至少可以直接找到基准数的这个位置
    while (left < right) {
        while (left < right && a[right] >= pivot) { //从右边找到比基准数小的那个
            right--;
        }
        while (left < right && a[left] <= pivot) {
            left++;
        }
        if (left < right) {
            swap(left, right);
        }
    }

    if (left <= right) { //在不出现越界的情况下,执行基准和相遇点的交换
        swap(pivotIndex, left);
        quickSortByRange(a, l, left - 1);
        quickSortByRange(a, left + 1, r);
    }
}
void quickSort(int a[], int n) {
    if (n <= 1) {
        return;
    }
    quickSortByRange(a, 0, n - 1);
}

插入排序

  • 插入排序关键在于插入,分割为排序和未排序部分,不断把右边的元素插入到左边的序列中,注意是相邻元素交换。
  • 时间复杂度:O(n^2), 空间复杂度 O(1)
void insertOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }
    
     //每次选定一个元素同前面的已排序的元素做对比,找到应该插入的位置
    for (int i = 1; i < n; i++) {
        int key = array[i];
        
        int j = i - 1;
        while (j >= 0) {
            if (key > array[j]) {
                swap(array, j, j+1);
            }
            else {
                break;
            }
            j--;
        }
        
    }
}

选择排序

  • 选择排序每次从未排序的队列中选择出最大或者最小元素,放到已排序的队列末尾。
  • 时间复杂度: O(n^2) , 空间复杂度: O(1)
///选择排序,降序,
void selectOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }

    //选择排序,每次从无序的被选的元素中找最大或者最小的放到有序的环境中
    for (int i = 0; i < n; i++){
        int selectIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] > array[i]) {
                selectIndex = j;
            }
        }
       swap(array, i, selectIndex);
    }
  }
}

其他

  • 因为快排拥有比较好的平均时间复杂度,所以快排用的范围相对来说更广一些。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • 某次二面时,面试官问起Js排序问题,吾绞尽脑汁回答了几种,深感算法有很大的问题,所以总计一下! 排序算法说明 (1...
    流浪的先知阅读 1,214评论 0 4
  • 平时很喜欢去蛋糕店,因为对甜点戒不了,连蛋糕店的小哥和我都很熟,有一次我去的时候人刚好不是很多,有两个女孩趴在玻璃...
    呓语姑娘阅读 537评论 4 2
  • 你跟自己对战 你中枪倒下 嘴张合着 含糊的声音 别人没听清你突然断气 你想要营造一场死亡 对这个世界撒最后一个谎 ...
    虚耗阅读 124评论 0 0
  • 老糖现在很紧张。 在一家人不多也不少的餐厅里等着对方开口说话,可对面却并排坐着拘谨的醪糟圆子君还有悠闲的烧鸡先生。...
    糖三角先森阅读 532评论 5 3