干货收藏:一文掌握十大经典排序算法(动态演示+代码)(一)

以前也零零碎碎发过一些排序算法,但排版都不太好,又重新整理一次,排序算法是数据结构的重要部分,系统地学习很有必要。


时间、空间复杂度比较


干货收藏:一文掌握十大经典排序算法(动态演示+代码)(一)



1 冒泡排序


算法思想:


比较相邻的元素。如果第一个比第二个大,就交换他们两个。


对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。


针对所有的元素重复以上的步骤,除了最后一个。


持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


代码:


void bubbleSort(int a[], int n)
{
  for(int i =0 ; i< n-1; ++i) 
  {
    for(int j = 0; j < n-i-1; ++j) 
    {
      if(a[j] > a[j+1])
      {
        int tmp = a[j] ;  //交换
        a[j] = a[j+1] ;  
        a[j+1] = tmp;
      }
    }
  }
}

2 选择排序


算法思想:


在未排序序列中找到最小(大)元素,存放到排序序列的起始位置


从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾


以此类推,直到所有元素均排序完毕


代码:


function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

3 插入排序


算法思想:


从第一个元素开始,该元素可以认为已经被排序


取出下一个元素,在已经排序的元素序列中从后向前扫描


如果该元素(已排序)大于新元素,将该元素移到下一位置


重复步骤3,直到找到已排序的元素小于或者等于新元素的位置


将新元素插入到该位置后


重复步骤2~5


插入排序动图演示


代码:


void print(int a[], int n ,int i){
  cout<<i <<":";
  for(int j= 0; j<8; j++){
    cout<<a[j] <<" ";
  }
  cout<<endl;
} 
void InsertSort(int a[], int n)
{
  for(int i= 1; i<n; i++){
    if(a[i] < a[i-1]){   //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
      int j= i-1;  
      int x = a[i];     //复制为哨兵,即存储待排序元素
      a[i] = a[i-1];           //先后移一个元素
      while(x < a[j]){   //查找在有序表的插入位置
        a[j+1] = a[j];
        j--;     //元素后移
      }
      a[j+1] = x;     //插入到正确位置
    }
    print(a,n,i);      //打印每趟排序的结果
  }
}
int main(){
  int a[15] = {2,3,4,5,15,19,16,27,36,38,44,46,47,48,50};
  InsertSort(a,15);
  print(a,15,15);
}

4 快速排序


算法思想:


选取第一个数为基准


将比基准小的数交换到前面,比基准大的数交换到后面


对左右区间重复第二步,直到各区间只有一个数



代码:


void QuickSort(vector<int>& v, int low, int high) {
    if (low >= high)  // 结束标志
  return;
    int first = low;  // 低位下标
    int last = high;  // 高位下标
    int key = v[first];  // 设第一个为基准
    while (first < last)
    {
  // 将比第一个小的移到前面
  while (first < last && v[last] >= key)
    last--;
  if (first < last)
    v[first++] = v[last];
  // 将比第一个大的移到后面
  while (first < last && v[first] <= key)
    first++;
  if (first < last)
    v[last--] = v[first];
    }
    //
    v[first] = key;
    // 前半递归
    QuickSort(v, low, first - 1);
    // 后半递归
    QuickSort(v, first + 1, high);
}

5 堆排序


堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。


算法思想:


将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;


将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];


由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。


代码:


#include <iostream>
#include <algorithm>
using namespace std;
// 堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。
void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点在范围内才做比较
  if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标,选择最大的
    son++;
  if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成,直接跳出函数
    return;
  else { //否则交换父子內容再继续子节点与孙节点比較
    swap(arr[dad], arr[son]);
    dad = son;
    son = dad * 2 + 1;
  }
    }
}
void heap_sort(int arr[], int len) {
    //初始化,i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
  max_heapify(arr, i, len - 1);
    //先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完成
    for (int i = len - 1; i > 0; i--) {
  swap(arr[0], arr[i]);
  max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
  cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

6 归并排序


归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。


算法思想: 1.把长度为n的输入序列分成两个长度为n/2的子序列; 2. 对这两个子序列分别采用归并排序; 3. 将两个排序好的子序列合并成一个最终的排序序列。


代码:

void print(int a[], int n){
  for(int j= 0; j<n; j++){
    cout<<a[j] <<"  ";
  }
  cout<<endl;
}
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
  int j,k;
  for(j=m+1,k=i; i<=m && j <=n ; ++k){
    if(r[j] < r[i]) rf[k] = r[j++];
    else rf[k] = r[i++];
  }
  while(i <= m)  rf[k++] = r[i++];
  while(j <= n)  rf[k++] = r[j++];
  print(rf,n+1);
}
void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
  int len = 1;
  ElemType *q = r ;
  ElemType *tmp ;
  while(len < lenght) {
    int s = len;
    len = 2 * s ;
    int i = 0;
    while(i+ len <lenght){
      Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
      i = i+ len;
    }
    if(i + s < lenght){
      Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
    }
    tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
  }
}
int main(){
  int a[10] = {2,3,4,5,15,19,26,27,36,38,44,46,47,48,50};
  int b[10];
  MergeSort(a, b, 15);
  print(b,15);
  cout<<"结果:";
  print(a,10);
}


上一篇:深度学习全网最全学习资料汇总之入门篇


下一篇:ML之RF&XGBoost:分别基于RF随机森林、XGBoost算法对Titanic(泰坦尼克号)数据集进行二分类预测(乘客是否生还)