生成随机数
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);
}
