十大排序算法

参考来自一像素的优质文章

1.冒泡排序(Bubble Sort)

时间复杂度为O(n^2),是一个稳定的排序算法，可以用一个flag判断，每一趟都进行检测，一旦有一趟a[j]<a[j+1]都成立，那么可以说已经完成排序，最好情况下O(n).

代码实现

//main.cpp
int main(){
int arr[] = { 1, 34, 11, 2, 6, 7, 3, 93, 1, 24, 5, 67, 23, 4, 2, 3, 1, 7, 8, 4, 2, 10 };
int len=sizeof(arr)/4;

bubble_sort(&arr[0],len);//或者下面的方式也可以
//bubble_sort(arr,len);
    
for (int i = 0; i < len; i++)
    cout << arr[i]<<" ";
cout << endl;

return 0;
}
/////////////////////////////////////////////////////////////////////////////////////
//bubble_sort.cpp
void bubble_sort(int * arr,int len){
//int len = sizeof(arr) / 4; 
    //在这里使用sizeof，计算的将是一个指针的长度，而不是一个数组的长度
    for (int i = 0; i < len - 1; i++){
    for (int j = i+1; j < len; j++){
        if (arr[i]>arr[j]){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

}

2.选择排序（Selection Sort）

是一个十分均衡的算法，最好最坏都是O(n^2)的复杂度，是一个不稳定算法。无法直接判断最好的情况。每次都选择最小的元素，和“第一个”元素交换位置。然后第一个元素下标加1，下一个元素吧变成第一个元素

代码实现

void selection_sort(int *arr, int len){
int min_index = 0, min_num;
if (len>0) min_num = arr[0];
for (int i = 0; i < len - 1; i++){
    min_index =i;
    min_num = arr[i];
    for (int j = i + 1; j < len; j++){//选择最小值，记录下标和值
        if (arr[j] < min_num){
            min_index = j;
            min_num = arr[j];
        }       
    }
    int tmp = arr[i];      //交换最小值到第一位
    arr[i] = arr[min_index];
    arr[min_index] = tmp;

}
}

3.插入排序（Insertion Sort）

平均复杂度为O(n^2)，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。对于大小为N的数组，当检索到第k位时(0=<k<N)，0~k-1位都已经是排好序的。

代码实现

void insertion_sort(int *arr, int len){
int current,index;
for (int i = 1; i < len; i++){
    index = i - 1;
    current = arr[i];
    while (index >=0){
        if (arr[index] <= current) //已排好序的最大数与当前要插入的数比较
            break;
        else { 
            arr[index + 1] = arr[index];
            index--;
        }
      }
      arr[index + 1] = current;
   }
}