排序

选择排序算法

 1 void select_sort(int arr[], size_t len)
 2 {
 3     for (int i = 0; i < len - 1; i++)
 4     {
 5         for (int j = i + 1; j < len;j++)
 6         {
 7             if (arr[i]>arr[j])
 8             {
 9                 int tempVal = arr[i];
10                 arr[i] = arr[j];
11                 arr[j] = tempVal;
12             }
13         }
14     }
15 }

冒泡排序算法

 1 void bubble_sort(int arr[], size_t len)
 2 {
 3     for (int i = 0; i < len-1;i++)
 4     {
 5         for (int j = 0; j < len - 1 - i;j++)
 6         {
 7             if (arr[j]>arr[j+1])
 8             {
 9                 int tempVal = arr[j];
10                 arr[j] = arr[j + 1];
11                 arr[j + 1] = tempVal;
12             }
13         }
14     }
15 }

插入排序算法优化过程

 1 void insert_sort1(int arr[], size_t len)
 2 {
 3     int tempVal;
 4     for (int i = 1; i < len; ++i)//确定插入过程中需要插入元素的下标i
 5     {
 6         for (int j = i - 1; j>=0; j--)//j为已序序列最后一个元素的下标
 7         {
 8             if (arr[j+1] < arr[j])//如果插入的元素和最后一个元素进行判断
 9             {
10                 tempVal = arr[j + 1];
11                 arr[j + 1] = arr[j];
12                 arr[j] = tempVal;
13             }
14             else
15                 break;
16         }
17     }
18 
19 }

 1 void insert_sort2(int arr[], size_t len)
 2 {
 3     int tempVal,j;
 4     for (int i = 1; i < len;++i)//确定插入过程中需要插入元素的下标i
 5     {
 6         tempVal = arr[i];//保存一下待插入的元素值
 7         for (j = i - 1; j>=0;j--)//j为已序序列最后一个元素的下标
 8         {
 9             if (tempVal<arr[j])//如果插入的元素和最后一个元素进行判断
10             {
11                 arr[j + 1] = arr[j];
12             }
13             else
14                 break;
15         }
16         arr[j + 1] = tempVal;//把保存的元素放在对应的位置
17     }
18 
19 }

 1 void insert_sort3(int arr[], size_t len)
 2 {
 3     int tempVal, j;
 4     for (int i = 1; i < len; ++i)//确定插入过程中需要插入元素的下标i
 5     {
 6         tempVal = arr[i];//保存一下待插入的元素值
 7         for (j = i - 1; j >= 0 && tempVal < arr[j]; j--)//j为已序序列最后一个元素的下标
 8         {
 9             arr[j + 1] = arr[j];
10         }
11         arr[j + 1] = tempVal;//把保存的元素放在对应的位置
12     }
13 }

 1 void insert_sort(int arr[], size_t len)
 2 {
 3     int tempVal, j;
 4     for (int i = 1; i < len; ++i)//确定插入过程中需要插入元素的下标i
 5     {
 6         tempVal = arr[i];//保存一下待插入的元素值
 7         j = i - 1;
 8         while( j >= 0 && tempVal < arr[j])//j为已序序列最后一个元素的下标
 9         {
10             arr[j + 1] = arr[j]; 
11             j--;
12         }
13         arr[j + 1] = tempVal;//把保存的元素放在对应的位置
14     }
15 
16 }

希尔排序（插入排序的优化）

 1 void shell_sort(int arr[], size_t len)
 2 {
 3     int tempVal, j;
 4     int jump = len >> 1;
 5     while (jump != 0)
 6     {
 7         for (int i = jump; i < len; ++i)//确定插入过程中需要插入元素的下标i
 8         {
 9             tempVal = arr[i];//保存一下待插入的元素值
10             j = i - jump;
11             while (j >= 0 && tempVal < arr[j])//j为已序序列最后一个元素的下标
12             {
13                 arr[j + 1] = arr[j];
14                 j-=jump;
15             }
16             arr[j + jump] = tempVal;//把保存的元素放在对应的位置
17         }
18         jump >>= 1;
19     }
20 }

桶排序（时间最快空间最大的排序）

 1 void radix_sort(int arr[],size_t len)//桶排序
 2 {
 3     int temp[10][10] = {};
 4     for (int n = 1; n < 1000;n*=10)
 5     {
 6         for (int x = 0; x < 10;x++)
 7         {
 8             for (int y = 0; y < 10;++y)
 9             {
10                 temp[x][y] = -1;//不一定是-1
11             }
12 
13         }
14         for (int i = 0; i < len;++i)
15         {
16             int tempIndex = (arr[i] / n) % 10;
17             temp[tempIndex][i] = arr[i];
18         }
19         int k = 0;
20         for (int x = 0; x < 10; x++)
21         {
22             for (int y = 0; y < 10; ++y)
23             {
24                 if (temp[x][y] != -1)
25                 {
26                     arr[k++] = temp[x][y];
27                 }
28             }
29         }
30 
31     }
32 
33 }

归并排序（递归合并）

 1 void _merge_in_arr(int arr[], int left, int mid, int right)//处理合并
 2 {
 3     //准备一个辅助数组
 4     int length = right - left + 1;//表示辅助数组长度
 5     int *pData = new int[length];//分配动态内存 保存数据
 6     //memset内存逐字节赋值 第一个参数是哪个内存 第二个参数赋什么值，第三个参数这个内存需要赋多大内存
 7     memset(pData, 0, sizeof(int)* length);
 8     //合并
 9     int low = left;//定义一个变量接一下左边第一个下标位置
10     int hig = mid + 1;//定义一个变量接一下右边区域的第一个赋值
11     int index = 0;//给辅助数组遍历的下标
12     while (hig<=right&&low<=mid)//左右区间都有数据 都没比较结束
13     {
14         while (low <= mid&&arr[low] <= arr[hig])//左边区间没有越界 并且左区间的数值<=右区间的数值
15         {
16             pData[index++] = arr[low++];
17         }
18         while (hig <= right&&arr[low] > arr[hig])//右边区间没有越界 并且右区间的数值>右区间的数值
19         {
20             pData[index++] = arr[hig++];
21         }
22     }
23     //到这一步，证明起码有一个区间是合并进了辅助数组
24     if (hig<=right)//证明右区间并没有完成合并，左区间是完成合并 把右区间剩下的数据直接拷贝到辅助数组即可
25         memcpy(&pData[index],&arr[hig],sizeof(int)*(right-hig+1));//内存拷贝有三个参数 表示把第二个参数的首地址拷贝到第一个参数的首地址里面 拷贝大小为第三个参数大小
26     if (low <= mid)
27         memcpy(&pData[index], &arr[low], sizeof(int)*(mid - low + 1));
28     memcpy(&arr[left], pData, sizeof(int)* length);
29     delete[] pData;
30 }
31 void _merge(int arr[], int left, int right)//通过递归把数组拆成两个部分
32 {
33     if (left >= right)//当左右下标一致时 区间内只有一个元素 不用再拆分
34         return;
35     //int mid = (right - left) >> 1;
36     int mid = ((right - left) >> 1) + left;
37     _merge(arr, left, mid);//递归左区间
38     _merge(arr, mid + 1, right);//递归右区间
39     //合并操作
40     _merge_in_arr(arr, left, mid, right);
41 }
42 void merge_sort(int arr[], size_t len)
43 {
44     _merge(arr, 0, len-1);
45 }

快速排序

 1 void quick_sort(int arr[], int low, int hight)
 2 {
 3     int t = arr[low];//确定标杆的值
 4     int f = low + 1;//表示指的数应该比标杆小
 5     int b = hight;//表示指的数应该比标杆大
 6     if (low >= hight)return;//表示只有一个元素 无需定位
 7     int tempVal;
 8     while (f<=b)//表示待定位的区间是存在的
 9     {
10         while (f<=b)
11         {
12             while (f <= b&&arr[f] <= t) f++;//一直找标杆大的元素
13             while (f <= b&&arr[b] >= t) b--;//一直找比标杆小的元素
14             if (f<b)//定位区间没有搜索完成
15             {
16                 tempVal = arr[f];
17                 arr[f] = arr[b];
18                 arr[b] = tempVal;
19                 f++;
20                 b--;
21             }
22         }
23         arr[low] = arr[b];
24         arr[b] = t;
25         quick_sort(arr, low, b - 1);
26         quick_sort(arr,b+1,hight);
27 
28          
29     }
30 }

二分查找

 1 int binarySeaarch(int arr[], int low, int hight, int findVal)
 2 {
 3     int mid = 0;//表示中间下标
 4     while (low <= hight)//表示区间存在
 5     {
 6         mid = ((hight - low) >> 1) + low;
 7         if (findVal == arr[mid])
 8             return mid;
 9         if (findVal < arr[mid])
10             hight = mid - 1;
11         if (findVal > arr[mid])
12             low = mid + 1;
13     }
14     return -1;
15 }

输出函数

1 void printArr(int arr[], int len)
2 {
3     for (int i = 0; i < len;++i)
4     {
5         printf("%d     ", arr[i]);
6     }
7     printf("
//===========================
");
8 }

主函数

 1 int main()
 2 {
 3     srand((size_t)time(nullptr));
 4     int arr[LEN];
 5     int arr1[LEN]; 
 6     int arr2[LEN];
 7     int arr3[LEN];
 8     int arr4[LEN];
 9     int arr5[LEN]; 
10     int arr6[LEN];
11     int arr7[LEN];
12     for (int i = 0; i < LEN;i++)
13     {
14         arr[i] = rand() % 900+100;
15         arr1[i] = arr[i];
16         arr2[i] = arr[i];
17         arr3[i] = arr[i];
18         arr4[i] = arr[i];
19         arr5[i] = arr[i];
20         arr6[i] = arr[i];
21         arr7[i] = arr[i]; 
22     }
23     printArr(arr, LEN);
24     select_sort(arr, LEN);
25     printArr(arr, LEN);
26     bubble_sort(arr1, LEN);
27     printArr(arr1, LEN);
28     insert_sort(arr2, LEN);
29     printArr(arr2, LEN);
30     shell_sort(arr3, LEN);
31     printArr(arr3, LEN);
32     radix_sort(arr4, LEN);
33     printArr(arr4, LEN);
34     insert_sort1(arr5, LEN);
35     printArr(arr5, LEN);
36     int ar[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
37     printf("%d
", binarySeaarch(ar, 0, 9, 10));
38     merge_sort(arr7, LEN);
39     printArr(arr7, LEN);
40     cin.get();
41     return 0;
42 }