排序、查找算法

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

// 未排序序列里两两交换，将最大值浮到已排序序列头部
void bubbleSort(vector<int>& nums)
{
    int len = nums.size();
    bool flag = false;
    for (int i = 0; i < len - 1; ++i){
        flag = false;
        for (int j = 0; j < len - i - 1; ++j)
        {
            if (nums[j] > nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
}
// 从未排序序列选择最小的，放入已排序序列末尾
void selectSort(vector<int>& nums)
{
    int len = nums.size();
    for (int i = 0; i < len - 1; ++i)
    {
        int min = i;
        for (int j = i + 1; j < len; ++j)
        {
            if (nums[min] > nums[j]) min = j;
        }
        int temp = nums[min];
        nums[min] = nums[i];
        nums[i] = temp;
    }
}
// 如果已排序序列的后一个值小于尾部，则放入已排序序列指定位置
void insertSort(vector<int>& nums)
{
    int len = nums.size();
    for (int i = 1; i < len; ++i)
    {
        if (nums[i - 1] > nums[i])
        {
            int temp = nums[i];   // 已排序的后一个
            int j = i;  // 其下标
            // 不断移动已排序序列
            for (; j > 0 && nums[j-1] > temp; --j)
                nums[j] = nums[j-1];
            // 先--j再判断，所以j为指定位置
            nums[j] = temp;
        }
    }
}
// 将未排序序列分为两半，对这两半分别使用归并排序，将排好序的两半合并成最终排序序列
void mergeSort(vector<int>& nums) {}
// 利用基准元素将序列分成小于基准元素和大于基准元素两个区间，再分别从两个区间内选择基准元素
// 划分两个区间，直到排好序
int Partition(vector<int>& nums, int low, int high)
{
    int pivot = nums[low];  // 基准元素
    while (low < high)  // 每次最多修改两个元素，直到左右区都划分好
    {
        // 比基准元素大
        while (low < high && nums[high] >= pivot) --high;
        // 放到小区间里
        nums[low] = nums[high];
        // 比基准元素小
        while (low < high && nums[low] <= pivot) ++low;
        // 放到大区间里
        nums[high] = nums[low];
    }
    // 区间中间放入基准元素
    nums[low] = pivot;
    return low;
}
void quickSort(vector<int>& nums, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(nums, low, high);
        // 序列根据基准元素划分成两个子序列
        quickSort(nums, low, pivot - 1);
        quickSort(nums, pivot+1, high);
    }
}
// 找到序列的最小最大值，并将序列元素放到哈希表里
// 再从最小到最大遍历哈希表，从头开始对序列进行赋值。
void countSort(vector<int>& nums)
{
    int maxV = 0;
    int minV = 999;
    unordered_map<int, int> bucket;
    for (auto n:nums)
    {
        if (maxV < n) maxV = n;
        if (minV > n) minV = n;
        bucket[n]++;
    }
    int sortedIndex = 0;
    for (int i = minV; i <= maxV; ++i)
    {
        while (bucket[i])
        {
            nums[sortedIndex++] = i;
            --bucket[i];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

template <typename T>
int binarySearch(vector<T>& nums, T value)
{
    int low = 0, high = nums.size() - 1;
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (nums[mid] > value) high = mid - 1;
        else if (nums[mid] < value) low = mid + 1;
        else return mid;
    }
    return -1;
}