0.测试框架

• 创建随机数数组void Create_RandomArr(int* arr,int n){}

// 产生随机数数组
// 随机产生 0~n-1 之间的随机数
void Create_RandomArr(int* arr,int n){
        srand(time(NULL));
        for(int i=0;i<n;i++){
                arr[i] = rand()%n;
        }
}

• 判断数组是否有序bool Judge_order(int* arr,int n,bool flag){}

// 判断数组是否有序
// true 默认升序 false 默认降序
bool Judge_order(int* arr,int n,bool flag){
        for(int i=0;i<n-1;i++){
                if(flag){
                        if(arr[i] > arr[i+1]) return false;
                }else{
                        if(arr[i] < arr[i+1]) return false;
                }
        }
        return true;
}

• 函数：交换两个数void swap(int* a,int* b){}

// 交换两个数
void swap(int* a,int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
}

• 函数：打印数组void PrintArr(int* arr,int n){}

// 打印数组
void PrintArr(int* arr,int n){
        for(int i=0;i<n;i++){
                printf("%d ",arr[i]);
        }
        printf("\n");
}

• qsort()函数的回调函数int cmp(const void* a,const void* b){}

// qsort()回调函数
int cmp(const void* a,const void* b){
        return *(int*)a - *(int*) b;
}

1.归并排序

1.1 方法

将给出的随机数组进行拆分，直到单个元素，形成有序数组，不断将两个有序数组进行合并。

• 递归形式：（完全二叉树）
  左 -> 返回上一层函数 -> 右 -> 返回上一层函数 -> 返回上上层函数

  
  
  归并排序过程

• 迭代形式：
  不在进行拆分，根据步长gap(1,2,4,8,...)，对于两个步长内的两个有序数组(每个数组的长度为gap)进行合并，直到步长超过或等于数组长度。
  步长从1开始，故下次迭代中每个步长内的数组均为有序数组。
  len为merge()后，数组的剩余长度
  

  归并排序过程2

迭代形式的三种情况

1.2 实现

1. 实现两个有序数组的合并

void merge(int* arr1,int n1,int* arr2,int n2){
        int i=0,j=0,k=0;
        int res[n1+n2];
        while(i<n1 && j<n2){
                if(arr1[i]<arr2[j]){
                        res[k++] = arr1[i++];
                }else{
                        res[k++] = arr2[j++];
                }
        }
        if(i<n1){
                while(i<n1) res[k++] = arr1[i++];
        }
        if(j<n2){
                while(j<n2) res[k++] = arr2[j++];
        }
        for(int i=0;i<k;i++){
                arr1[i] = res[i];
        }
}

优化：

void merge2(int* arr,int n,int mid){
        int res[n];
        int i=0,j=mid,k=0;
        while(i<mid && j<n){
                res[k++] = (arr[i] < arr[j])?arr[i++]:arr[j++];
        }
        if(i<mid) memcpy(res+k,arr+i,(mid-i)*sizeof(int));
        if(j<n) memcpy(res+k,arr+j,(n-j)*sizeof(int));

        memcpy(arr,res,n*sizeof(int));
}

2. 拆分并合并数组

• 递归形式
  对应merge()

void Merge_sorting(int* arr,int n){
        if(n>1){
                int mid = n/2;
                Merge_sorting(arr,mid);              // 左 [0,mid)
                Merge_sorting(arr+mid,n-mid);        // 右 [mid,n)
                merge(arr,mid,arr+mid,n-mid);
        }
}

对应merge2()

void Merge_sorting2(int* arr,int n){
        if(n >1){
                int mid = n/2;
                Merge_sorting2(arr,mid);
                Merge_sorting2(arr+mid,n-mid);
                merge2(arr,n,mid);
        }
}

• 迭代形式

int min(int a,int b) {return a<b?a:b;}

根据步长进行遍历。

void submerge(int* arr,int n,int gap){
        int len = n;
        for(int i=0;i+gap<n;i += 2*gap){
                merge2(arr+i,min(2*gap,len),gap);
                len -= 2*gap;
        }
}

划分步长

void Merge_sorting3(int* arr,int n){
        for(int i=1;i <=n;i *= 2){
                submerge(arr,n,i);
        }
}

1.3 复杂度

• 时间复杂度
  一共拆分log2n次，每次比较n个元素，一共比较nlog2n次

• 空间复杂度 O(n)

2.快速排序

2.1 方法

将每次迭代过程中的数组的首元素作为基准数key，先从尾进行遍历，找到第一个小于基准数的元素arr[j],然后从头开始遍历，找到第一个大于基准数的元素arr[i]，交换两个元素的值，直到两个数遍历到相同位置，在遍历过程中i<j,将基准数与最终位置所在的数进行交换-确定基准数key的位置，在依次确定其他基准数的位置。

快速排序过程

2.2 实现

1.确定基准数在数组中的位置，返回确定位置的下标

int partition(int* arr,int n){
        int key = arr[0];
        int i=0,j=n-1;
        while(i<j){
                while(i<j && arr[j] >= key) j--;
                if(i>=j) break;
                while(i<j && arr[i] <= key) i++;
                if(i>=j) break;

                swap(arr+i,arr+j);
        }
        swap(arr,arr+i);
        return i;
}

2.根据基准数的位置，对于基准数左右两部分分别进行重新排序

void Quick_sorting(int* arr,int n){
        if(n>1){
                int index = partition(arr,n);
                Quick_sorting(arr,index);
                Quick_sorting(arr+index+1,n-index-1);
        }
}

2.3 复杂度

• 时间复杂度
  一共拆分log2n次，每次比较n个元素，一共比较nlog2n次
• 空间复杂度 O(log2n)

3.希尔排序

3.1 方法

选择一定的步长gap，将列表分为若干个子列表sublist，对每个子列表sublist进行插入排序，依次减少步长gap，重复上述操作，直到gap为1.

希尔排序过程

3.2 实现

1.划分gap并执行排序

void insert3(int* arr,int n,int gap){
        int insert_data = arr[n-1];
        for(int i=n-gap-1;i>=0;i-=gap){
                if(arr[i] > insert_data){
                        arr[i+gap] = arr[i];
                }else{
                        break;
                }
        }
}

2.根据gap执行插入排序

void Insert_sorting3(int* arr,int n,int gap){
        for(int i=gap;i<=n;i++){
                insert3(arr,i,gap);
        }
}

3.根据gap插入

void Shell_sorting(int* arr,int n){
        for(int i = n/2;i>=1;i /= 2){
                Insert_sorting3(arr,n,i);
        }
}

3.3 复杂度

• 时间复杂度 O(nlog2n)
• 空间复杂度 O(1)

比较

算法选择标准