美文网首页
Sorting and Searching

Sorting and Searching

作者: 一斗 | 来源:发表于2019-01-24 11:30 被阅读0次

Sorting

1. Bubble Sort（冒泡排序）

  1. 从第一位开始和其下一位进行比较，如果前者大，则交换位置，这样一轮下来，最大值就在最末尾
  2. 第二轮循环范围从第一位至倒数第二位，依次类推

冒泡排序可以优化，即设置一个标志位，用来标记每轮循环是否有发生至少一次位置交换，如果一次位置交换也没有发生，说明排序已经完成，可以终止排序过程。

bubbleSort.cpp

#include<cstdio>

void shortBubbleSort(int list[], int len) {
    bool ordered = true;
    int passNum = len-1;
    while(passNum>0 && ordered) {
        ordered = false;
        for(int j=0; j<passNum; j++) {
            if(list[j]>list[j+1]) {
                ordered = true;
                int temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;
            }
        }
        passNum--;
    }
}

int main(){
    int list[]={5, 2, 7, 11, 89, 45, 32, 12, 56};
    int len=sizeof(list)/sizeof(list[0]);
    shortBubbleSort(list, len);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func bubbleSort(list []int) {
    passNum := len(list) - 1
    ordered := true
    for passNum > 0 && ordered {
        ordered = false
        for j := 0; j < passNum; j++ {
            if list[j] > list[j+1] {
                temp := list[j]
                list[j] = list[j+1]
                list[j+1] = temp
                ordered = true
            }
        }
        passNum--
    }
}

func main() {
    list := []int{10, 4, 7, 3, 5, 9, 8, 2, 1, 6}
    bubbleSort(list)
    fmt.Println(list)
}

由于两层循环，可知冒泡排序的时间复杂度为O(n2)

2. Selection Sort（选择排序）

选择排序和冒泡排序的思路基本一样，只是它每一轮循环只记录下最大值的位置，然后交换最大值和末尾的位置，即每一轮循环结束才发生依次位置交换，而不像冒泡排序每次比较都可能发生交换。

selectSort.cpp

#include<cstdio>

void selectSort(int list[], int len) {
    for(int i=len-1; i>=0; i--) {
        int maxIndex = 0;
        for(int j=1; j<=i; j++) {
            if(list[j]>list[maxIndex]) {
                maxIndex = j;
            }
        }
        int temp = list[i];
        list[i] = list[maxIndex];
        list[maxIndex] = temp;
    }
}

int main() {
    int list[]={5, 2, 7, 11, 89, 45, 32, 12, 56};
    int len=sizeof(list)/sizeof(list[0]);
    selectSort(list, len);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func selectSort(list []int) {
    for i := len(list) - 1; i >= 0; i-- {
        maxIndex := 0
        for j := 1; j <= i; j++ {
            if list[j] > list[maxIndex] {
                maxIndex = j
            }
        }
        temp := list[maxIndex]
        list[maxIndex] = list[i]
        list[i] = temp
    }
}

func main() {
    list := []int{10, 4, 7, 3, 5, 9, 8, 2, 1, 6}
    selectSort(list)
    fmt.Println(list)
}

同样两层循环，时间复杂度是O(n2)

3. Insertion Sort（插入排序）

插入排序的思想是假设有一个已经排好序的队列（升序），然后来了一待排序的值，先排在队尾，然后从其前一个值开始比较，如果前一个值大，则把前一个值往后移一位，直至不满足前一个值大或到了队首，此时的位置存放该待排序值。

插入排序把队列的第一个元素看作已排好序的队列，然后执行前面的操作。

insertSort.cpp

#include<cstdio>

void insertSort(int list[], int len) {
    for(int i=1; i<len; i++) {
        int pos = i;
        int temp = list[pos];
        while(pos>0 && list[pos-1]>temp) {
            list[pos] = list[pos-1];
            pos--;
        }
        list[pos] = temp;
    }
}

int main() {
    int list[]={5, 2, 7, 11, 89, 45, 32, 12, 56};
    int len=sizeof(list)/sizeof(list[0]);
    insertSort(list, len);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func insertSort(list []int) {
    for i := 1; i < len(list); i++ {
        pos := i
        temp := list[pos]
        for pos > 0 && list[pos-1] > temp {
            list[pos] = list[pos-1]
            pos--
        }
        list[pos] = temp
    }
}

func main() {
    list := []int{10, 4, 7, 3, 5, 9, 8, 2, 1, 6}
    insertSort(list)
    fmt.Println(list)
}

插入排序的时间复杂度也是O(n2)

4. Shell Sort（希尔排序）

希尔排序是在插入排序的基础上，将原始队列分成几个小的队列分别进行插入排序，来提高排序的速度。

shellSort.cpp

#include<cstdio>

void gapInsertSort(int list[], int len, int start, int gap) {
    for(int i=start+gap; i<len; i+=gap) {
        int pos = i;
        int temp = list[pos];
        while(pos>=gap && list[pos-gap]>temp) {
            list[pos] = list[pos-gap];
            pos-=gap;
        }
        list[pos] = temp;
    }
}

void shellSort(int list[], int len) {
    int sublistCount = len/2;
    while(sublistCount>0) {
        for(int i=0; i<sublistCount; i++) {
            gapInsertSort(list, len, i, sublistCount);
        }
        sublistCount /= 2;
    }
}

int main() {
    int list[]={5, 2, 7, 11, 89, 45, 32, 12, 56};
    int len=sizeof(list)/sizeof(list[0]);
    shellSort(list, len);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func gapInsertSort(list []int, start int, gap int) {
    for i := start + gap; i < len(list); i += gap {
        pos := i
        temp := list[pos]
        for pos >= gap && list[pos-gap] > temp {
            list[pos] = list[pos-gap]
            pos -= gap
        }
        list[pos] = temp
    }
}

func shellSort(list []int) {
    sublistCount := len(list) / 2
    for sublistCount > 0 {
        for i := 0; i < sublistCount; i++ {
            gapInsertSort(list, i, sublistCount)
        }
        sublistCount /= 2
    }
}

func main() {
    list := []int{10, 4, 7, 3, 5, 9, 8, 2, 1, 6}
    shellSort(list)
    fmt.Println(list)
}

希尔排序通过排序递增的子序列提升了插入排序的效率，时间复杂度介于O(n)和O(n2)

5. Merge Sort（归并排序）

归并排序采用的是分治法思想，它是一种递归的算法，持续对半分割队列，直至队列为空或只含有一个元素，然后进行合并操作。

mergeSort.cpp

#include<cstdio>

const int maxn=100;
// 排序两个有序序列
void mergeTwoList(int l1[], int len1, int l2[], int len2, int l3[]) {
    int i=0, j=0, index=0;
    while(i<len1 && j<len2) {
        if(l1[i]>=l2[j]) {
            l3[index++]=l2[j++];
        } else {
            l3[index++]=l1[i++];
        }
    }
    while(i<len1) {
        l3[index++]=l1[i++];
    }
    while(j<len2) {
        l3[index++]=l2[j++];
    }
}

void merge(int list[], int left1, int right1, int left2, int right2) {
    int temp[maxn], index=0;
    int i=left1, j=left2;
    while(i<=right1 && j<=right2) {
        if(list[i]>=list[j]) {
            temp[index++]=list[j++];
        } else {
            temp[index++]=list[i++];
        }
    }
    while(i<=right1) {
        temp[index++]=list[i++];
    }
    while(j<=right2) {
        temp[index++]=list[j++];
    }
    for(int n=0; n<index; n++) {
        list[left1+n]=temp[n];
    }
}

void mergeSort(int list[], int left, int right) {
    if(left<right) {
        int mid=(left+right)/2;
        mergeSort(list, left, mid);
        mergeSort(list, mid+1, right);
        merge(list, left, mid, mid+1, right);
    }
}

int main() {
    int list[]={5, 7, 2, 4, 8, 1, 3, 10, 9, 6};
    int len = sizeof(list)/sizeof(list[0]);
    mergeSort(list, 0, len-1);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func merge(list []int, left1 int, right1 int, left2 int, right2 int) {
    temp := []int{}
    i := left1
    j := left2
    for i <= right1 && j <= right2 {
        if list[i] >= list[j] {
            temp = append(temp, list[j])
            j++
        } else {
            temp = append(temp, list[i])
            i++
        }
    }
    for i <= right1 {
        temp = append(temp, list[i])
        i++
    }
    for j <= right2 {
        temp = append(temp, list[j])
        j++
    }
    n := len(temp)
    for k := 0; k < n; k++ {
        list[left1+k] = temp[k]
    }
}

func mergeSort(list []int, left int, right int) {
    if left < right {
        mid := (left + right) / 2
        mergeSort(list, left, mid)
        mergeSort(list, mid+1, right)
        merge(list, left, mid, mid+1, right)
    }
}

func main() {
    list := []int{10, 4, 7, 3, 5, 9, 8, 2, 1, 6}
    mergeSort(list, 0, len(list)-1)
    fmt.Println(list)
}

归并排序的时间复杂度是O(nlogn)，但它需要额外的空间用于排序过程。

6. Quick Sort（快速排序）

快速排序的思想是在队列中随机选择一个值，然后队列中比该值小的值排在其左边，比该值大的值排在其右边，对于左右两边的子队列重复使用这种方法，最终完成排序。

quickSort.cpp

#include<cstdio>

int patition(int list[], int left, int right) {
    int temp = list[left];
    while(left<right) {
        while(left<right && list[right]>=temp) right--;
        list[left] = list[right];
        while(left<right && list[left]<temp) left++;
        list[right] = list[left];
    }
    list[left] = temp;
    for(int n=0; n<10; n++) {
        printf("%d ", list[n]);
    }
    printf("\n");
    return left;
    
}

void quickSort(int list[], int left, int right) {
    if(left<right) {
        int pos = patition(list, left, right);
        quickSort(list, left, pos-1);
        quickSort(list, pos+1, right);
    }
} 

int main() {
    int list[]={14,17,13,15,19,10,3,16,9,12};
    int len = sizeof(list)/sizeof(list[0]);
    quickSort(list, 0, len-1);
    for(int n=0; n<len; n++) {
        printf("%d ", list[n]);
    }
    return 0;
}

go版

package main

import "fmt"

func patition(list []int, left int, right int) int {
    temp := list[left]
    for left < right {
        for left < right && list[right] >= temp {
            right--
        }
        list[left] = list[right]
        for left < right && list[left] < temp {
            left++
        }
        list[right] = list[left]
    }
    list[left] = temp
    return left
}

func quickSort(list []int, left int, right int) {
    if left < right {
        pos := patition(list, left, right)
        quickSort(list, left, pos-1)
        quickSort(list, pos+1, right)
    }
}

func main() {
    list := []int{6, 4, 7, 3, 5, 10, 8, 2, 1, 9}
    quickSort(list, 0, len(list)-1)
    fmt.Println(list)
}

快速排序的时间复杂度是O(nlogn)，但当分割点不靠近列表中间时，退化到O(n2)

总体思路是选取一个元素，比该元素大的位于其右边，小的置于其左边。
步骤：

  1. 采用左右两边同时遍历的方式
  2. 初始左边索引left=0，右边索引right=len-1
  3. 左边第一个值赋值给temp
  4. 然后从右边索引开始递减遍历与temp比较，s[right]大或等于，继续遍历；s[right]小，则将此时s[right]赋值给s[left]。然后从左边开始递增遍历比较，如果s[left]小，则继续遍历；s[left]大，则将此时s[left]赋值给s[right]。最后将temp赋值给此时s[left]。这样原数组第一个值位置确认了，记为pos。
  5. 然后把[0, pos-1]和[pos+1, right]作为两组数组按照步骤1到4进行，left>=right结束。

Searching

  1. 顺序查找对于有序和无序列表的时间复杂度都是O(n)
  2. 有序列表使用二分查找的时间复杂度是O(logn)

binarySearch.cpp

#include<cstdio>

// 有序序列元素不重复
int binary_search(int list[], int left, int right, int num) {
    int mid;
    while(left<=right) {
        mid = (left+right)/2;
        if(list[mid]==num) {
            return mid;
        }
        else if(list[mid]>num) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return -1;
}
// 有序序列元素可重复, 查找第一个
int lower_bound(int list[], int left, int right, int num) {
    int mid;
    while(left<right) {
        mid = (left+right)/2;
        if(list[mid]>=num) {
            right = mid;
        }
        else {
            left = mid+1;
        }
    }
    if(list[left]==num) {
        return left;
    }
    else {
        return -1;
    };
}

int main() {
    const int LEN = 5;
    int list[LEN]={0};
    for(int i=0; i<LEN; i++) {
        scanf("%d", &list[i]);
    }
    int left=0, right=LEN-1, num=9;
    int index = binary_search(list, left, right, num);
    int lower = lower_bound(list, left, right, num);
    printf("%d %d\n", index, lower);
    return 0;
}

go版

package main

import "fmt"

func binarySearch(list []int, num int) int {
    left := 0
    right := len(list) - 1
    for left <= right {
        mid := (left + right) / 2
        if list[mid] == num {
            return mid
        } else if list[mid] > num {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

func main() {
    list := []int{1, 2, 3, 5, 7, 9}
    index := binarySearch(list, 4)
    fmt.Println(index)
}

相关文章

  • Sorting and Searching

    Remove Duplicates from Sorted Array Merge Sorted Array So...

  • Sorting and Searching

    Sorting 1. Bubble Sort（冒泡排序） 从第一位开始和其下一位进行比较，如果前者大，则交换位置，...

  • 笨办法学C 练习35：排序和搜索

    练习35：排序和搜索 原文：Exercise 35: Sorting And Searching 译者：飞龙 这个...

  • Basic Algorithm

    Sorting Algorithm Setup and Driver Program Each sorting a...

  • Harry Potter and The Sorcerer's

    Chapter 7 The Sorting Hat Sorting was a very important ce...

  • 《searching》

    通过我并不专业的眼光来看，这部电影最吸引我的无疑是表达形式。数字时代，全片都是由数字媒体连接而成的。所以更难得的反...

  • 《SEARCHING》

    微信写每月感受，简书写其他感受。

  • Comparable vs Comparator

    sorting 排序 sorting-in-javaJava中提供了Arrays.sort()和Collectio...

  • Sorting

    本文是我正在写的gitbook上的书Algorithms一个章节，由于是记录课程的内容，所以下文都是英文，见谅。 ...

  • Sorting

    排序与相关性 1、排序默认是根据相关性_score进行降序排序。filter会导致_score为0，如果0分对我们...

网友评论

      本文标题：Sorting and Searching

      本文链接：https://www.haomeiwen.com/subject/gndyjqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Sorting and Searching|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！