数据结构与算法之十大排序算法

• 十大排序算法
• • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

秋招对我好点！

算法的理论就不写了，网上有很多，可以去找一波，有些必要的细节我会在代码的注释中写。

顾名思义，把最大的值或者最小的值一个一个地冒出来。

// 翻转函数
void swap(vector& num,int a,int b){  // 需要使用引用传递 改变num的值
    int tmp = num[a];
    num[a] = num[b];
    num[b] = tmp;
}

void bulleSort(vector &num,int n){
    if (n <= 1) return;
    bool is_swap;   
    for(int i=0;i // 只需要遍历n-1次就行  
        is_swap = false;
        for(int j=0;j // 每次得到一个最大值  所以只需要遍历到前一个冒出的值前就行
            if(num[j]>num[j+1]){
                swap(num,j,j+1);
                is_swap = true;
            }
        }
        if(!is_swap) break; // 如果is_swap为false 说明，没有翻转  遍历提前结束
    }
}

分已排序区间和未排序区间。每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

void selectSort(vector &num,int n){
    if(n<=1) return;
    int min_index;  
    for(int i=0;i
        min_index = i;  
        for(int j=i+1;j
            if(num[j]
                min_index  = j;   // 每次都寻找最小的值 与i的值交换
            }
        }
        swap(num,i,min_index);
    }
}

分为已排序和未排序 初始已排序区间只有一个元素 就是数组第一个 遍历未排序的每一个元素在已排序
区间里找到合适的位置插入并保证数据一直有序。

void insertSort(vector &num,int n){
    if(n<=1) return;
    for(int i=0;i
        // 当前需要排序的值 num[i]
        for(int j=i;j>0 && num[j] // 遍历之前
            // 找到num[i]的位置 插进去
            swap(num,j,j-1);
        }
    }
}

通过将比较的全部元素分为几个区域来提升插入排序的性能，这样可以让一个元素可以一次性地朝最终位置前进一大步，然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到现在，数据几乎已经排好了。

void shellSort(vector &num,int n){
    if(n<=1) return;
    for(int gap = n/2;gap>0;gap/=2){  // 到最后一步 gap=1
        for(int i=gap;i
            for(int j=i;j-gap>=0 && num[j-gap]>num[j];j-=gap){
                swap(num,j,j-gap);
            }
        }
    }
}

用两个游标 i 和 j,分别指向 A[p…q] 和 A[q+1…r] 的第一个元素。比较这两个元素 A[i] 和 A[j],如果 A[i]<=A[j],我们就把 A[i] 放入到临时数组 tmp,并且 i 后移一位,否则将 A[j] 放入到数组 tmp,j 后移一位。
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

先局部有序，再整体有序！

void merge(vector&num,int l,int middle,int r){
    vector tmp;
    int i=l;
    int j=middle+1;
    // 比较小的数据添加到临时数组里
    while(i<=middle && j<=r){
        if(num[i]
            tmp.push_back(num[i++]);
        }else{
            tmp.push_back(num[j++]);
        }
    }
    while(i<=middle){
        tmp.push_back(num[i++]);
    }
    while (j<=r){
        tmp.push_back(num[j++]);
    }
    for(int i=0;i
        num[l+i] = tmp[i];
    }
}

void mergeSort(vector& num,int l,int r){ // r是长度
    if(l==r) return;  //递归是让数组中的每个数单独成为长度为1的区间
    int middle = l + (r-l)/2; // 取中段
    // 分治
    mergeSort(num,l,middle);
    mergeSort(num,middle+1,r);
    merge(num,l,middle,r);

}

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

void quickSort(vector &num,int l,int r){
    if(l+1 >= r) return; // 划分完毕
    int first = l,last = r-1,key = num[first];  // 选取first位置为比较点
    // 分成两个部分 后一部分 比前一部分要大
    while(first

        while(first=key) last--; // 右指针  直到找到一个比key要小的数
        num[first] = num[last]; // 将这个数放到first的位置

        while(first 
堆排序 
原理
 大顶堆： 节点元素值大于左右孩子的元素值，将待排序数组构建成一个大顶堆，根节点为最大值，将这个值与最后一个值交换位置，再对前n-1个元素构建大顶堆操作，获得最大值后交换位置，不断循环前面的操作便能得到排序后的数组。
 
void adjust(vector &nums, int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left nums[maxIdx]) maxIdx = left;
    if(right nums[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(nums[maxIdx], nums[index]);
        adjust(nums, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(vector& nums, int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(nums, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(nums[0], nums[i]);           // 将当前最大的放置到数组末尾
        adjust(nums, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}
 
计数排序 
计数排序是一种线性排序算法，不需要进行比较，时间复杂度为O(n)
 
void countSort(vector& nums){
    int maxVal = *max_element(nums.begin(),nums.end());
    int len = nums.size();
    if(len<1) return;
    vector count(maxVal+1,0);
    vector tmp(nums);

    for(auto x:nums){
        count[x]++;
    }

    // 统计
    for(int i=1;i<=len;++i){
        count[i] += count[i-1];
    }

    // 排序
    for(int i =len-1;i>=0;--i){
        nums[count[tmp[i]]-1] = tmp[i];
        count[tmp[i]]--;
    }
}
 
桶排序 
原理 将元素放进有限个桶里 对桶进行排序
 
void bucketSort(vector &nums) {
    if (nums.size() == 0) return;

    int high = *std::max_element(nums.begin(), nums.end());
    int low = *std::min_element(nums.begin(), nums.end());

    int n = high - low + 1;
    vector bucket(n);
    vector res;

    for(auto num:nums) bucket[num-low]++;

    for(int i=0;i
        for(int j=0;j
            res.push_back(i+low);
        }
    }

    // 重新赋值
    for(int i=0;i
        nums[i] = res[i];
    }
}
 
基数排序 
原理 按照位来排序
 
int getMaxLen(vector& nums){
    int max_len = INT_MIN;
    for(auto x:nums){
        int c = 0;
        while(x>0){
            c++;
            x/=10;
        }
        max_len = max(max_len,c);
    }
    return max_len;
}
void radizSort(vector& nums){
    // 位间的排序是利用桶排序
    const int BUCKETS = 10;
    vector> buckets(BUCKETS);
    int max_len = getMaxLen(nums);

    // 按照低位到高位进行基数排序
    int r = 1;
    for(int i=0;i< max_len;++i){
        // 放入桶中
        for(auto s:nums){
            int k = s/r;
            int q = k%BUCKETS;
            buckets[q].push_back(std::move(s));
        }

        // 遍历桶
        int index = 0;
        for(vector & thisBuicket:buckets){  // 用个引用就对了
            for(auto s:thisBuicket){
                nums[index++] = std::move(s);
            }
            thisBuicket.clear();
        }
        r *=10;
    }
}