排序算法（原理及实现）

生成随机数

int * getrand(int min, int max, int len){
       int* arr = (int*)malloc(sizeof(int)*len);
       for(int i = 0; i < len; ++i) {
            arr[i] = rand() % (max-min+1) + min;
      }
      return arr;
}

一、冒泡排序

算法原理：

比较两个相邻的元素，将值大的元素右移。

算法思路：

首先第一个元素和第二个元素比较，如果第一个大，则二者交换，否则不交换；然后第二个元素和第三个元素比较，如果第二个大，则二者交换，否则不交换……一直执行下去，最终最大的那个元素被交换到最后，一趟冒泡排序完成。最坏的情况是排序是逆序的。

算法过程:

image.png

{1}{68,35,70,25,79,59,63,65}

{1,25}{68,35,70,79,59,63,65}

算法实现:

void bubbleSort(int* arr,int len){
    int t;
    for (int i = 0; i < len - 1; i++)
    {   
        for (int j = 0; j < len - 1 - i; ++j){
            if (arr[j] > arr[j+1])
            {       
                    t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
            }
        }
    }
}

插入排序

原理：基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

栗子：我们有一个数组 arr[10] = {42,68,35,1,70,25,79,59,63,65};

思路：第一次循环
arr[0] 42与arr[1]比较 42 < 68 last不变
42 68 35 1 70 25 79 59 63 65
arr[0] 42与arr[2]比较 42 > 35 这时候让arr[1]与arr[2]互换 last自增 数组：
42 35 68 1 70 25 79 59 63 65
以此类推
42 35 1 68 70 25 79 59 63 65
42 35 1 68 70 25 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
当结束循环 arr[last] 与 原本的互换
25 35 1 42 70 68 79 59 63 65

void swap(int* arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
}
void QuickSort(int* arr ,int left, int right){
    if(left >= right)   // 若数组包含的元素少于两个
        return ;
    int last = left;    // 设左边元素为子集划分元素
    for(int i= left + 1; i<= right; i++){ // 划分子集
        if(arr[i] < arr[left]){
            swap(arr, ++last, i);  // index 跟
        }
        printf("%d %d %d\n",i, arr[i],arr[left]);
        //printArray(arr,10);
    }   
    swap(arr, left, last);          //回复划分子集的元素
    QuickSort(arr,left,last-1);
    QuickSort(arr,last+1,right);    
}