网站设计模式,摄影作品哪里看,债权债务交易网站开发,宁夏网站建设多少钱文章目录 前言1.插入排序#xff08;InsertSort#xff09;1.1 核心思路1.2 实现代码 2.选择排序#xff08;SelectSort#xff09;2.1 核心思路2.2 实现代码 3.冒泡排序#xff08;BubbleSort#xff09;3.1 核心思路3.2 实现代码 4.希尔排序#xff08;ShellSort… 文章目录 前言1.插入排序InsertSort1.1 核心思路1.2 实现代码 2.选择排序SelectSort2.1 核心思路2.2 实现代码 3.冒泡排序BubbleSort3.1 核心思路3.2 实现代码 4.希尔排序ShellSort4.1 核心思路4.2 实现代码 前言 在日常生活中我们常常要将各种各样的数据进行排序例如我要将班上的学生按照数学成绩从大到小的排序像这种一般情况编译器自带的sort函数就能满足我们的要求。但是假如我要将班上姓刘的学生按照数学成绩从大到小的排序呢 这种时候编译器自带的sort函数无法满足需求我们就需要自己定义一个排序函数。 下面我就要介绍目前的八大排序的原理代码以及时间空间复杂度。 1.插入排序InsertSort
1.1 核心思路 直接插入排序的核心思路是先分组再比较。 例如上面的数组有六个数。那么我们就可以先把[3,6]分成一组进行比较得到[3,6]数组。 再把[3,6,7]分成一组进行比较得到[3,6,7]数组。再把[3,6,7,1]分成一组得到[1,3,6, 7]数组。 以此类推得到[1,2,3,4,6,7]数组。 1.2 实现代码
// 插入排序
//插入排序的核心思路就是把i个数分成一组让第i个数与第i1个数进行比较
//把较大的数放在后面
void InsertSort(int* arr, int n)
{for (int i 0; i n - 1; i){int end i;//把i个数分成一组int tmp arr[end 1];//记录最后一个数while (end 0){//把i 2个数分成一组当 end 0 时//说明这一组的数没有全部比较循环比较大小if (arr[end] tmp){//位于end的数大于最后一个数arr[end 1] arr[end];//把位于end的数赋值给end 1的位置end--;//end--比较下一个数}else {break;}}arr[end 1] tmp;//退出while循环有两种情况//1.end减少到-1说明这一组的数均大于最后一个数//这样end1 0,把最后一个数赋值给0的位置//2.break提前跳出循环说明此时end的数小于最后一个数//那么把最后一个数放在end 1的位置}
}2.选择排序SelectSort
2.1 核心思路 选择排序的核心思路是先找到当前数组中的最大和最小数再放到相应的位置。 例如上面的数组选择排序中我们会定义好第一个位置0和最后一个位置size - 1再从数组中找到最小1和最大数7再把1和7放到相应的位置上。 再定义好第二个位置1和倒数第二个位置size - 2再从数组中找到第二小2和 第二大的数6再把2和6放到相应的位置上。 以此类推直到所有的数排序完。 2.2 实现代码
// 选择排序
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;//定义最小数据和最大数据的位置while (begin end)//当begin小于end时说明数组中的数据没有比较完循环比较{int mini begin, maxi begin;//先定义一个最小数和最大数for (int i begin 1; i end; i)//找大找小从第二个数开始比较{if (arr[i] arr[maxi])//当前数组轮到的数大于当前的最大数那么这个数就是新的最大数{maxi i;}if (arr[i] arr[mini])//当前数组轮到的数小于当前的最小数那么这个数就是新的最小数{mini i;}}if (maxi begin)//防止数组中全是相同的数导致maxi没有改变{maxi mini;}Swap(arr[mini], arr[begin]);//让最小的数与第一个数进行交换Swap(arr[maxi], arr[end]);//让最大的数与第二个数进行交换begin;//已经找到最小的数需要找第二小的数所以begin--end;//已经找到最大的数需要找第二大的数所以end--}
}3.冒泡排序BubbleSort
3.1 核心思路 冒泡排序的核心思路是暴力比较所有的数都比较一遍。 例如上面的数组将3与剩下所有的数字比较3大于1则把3放在1的位置1放在3的位置。 所有的数比较完成后就能得到有序的数组。 3.2 实现代码
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i)//找好第一个数{for (int j i 1; j n; j)//从第二个数开始{if (arr[i] arr[j])//所有的数与第一个数进行比较{Swap(arr[i], arr[j]);//如果第一个数大于比较的数则交换这两个数}}}
}4.希尔排序ShellSort
4.1 核心思路 希尔排序的核心思路是将数组分成若干个小组小组先进行预排序小组预排序完成后再将 所有的组合并并且进行排序。 例如上面的数组将数组分成三分之一则得到[3,6][7,1][4,2]三个数组。先对这三个数组进行排序得到[3,6][1,7][2,4]三个数组。 然后将这三个数组合并成两个数组得到[3,6,1][7,2,4]两个数组。再对[3,6,1][7,2,4]进行排序。得到[1,3,6][2,4,7]两个数组。 再将这两个数组合并得到[1,3,6,2,4,7],排序得到[1,2,3,4,6,7]。 4.2 实现代码
// 希尔排序
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;//将数组分成三分之一。 1 是为了防止gap 3从而导致gap / 3 0//同时for循环结束时再将数组进行细分for (int i 0; i n - gap; i)//由于数组被分成三分之一个所以数组的大小也变为三分之一{int end i;//第一个小组的第一个成员i之后就是第二个小组的第一个成员int tmp arr[end gap];//第一个小组的最后一个成员i之后就是第二个小组的最后一个成员while (end 0)//{if (arr[end] tmp)//当第一个小组里的第一个成员大于最后一个成员时{arr[end gap] arr[end];//把第一个成员放到最后一个成员的位置end - gap;//由于开始比较的是所有组的第一个成员//当end gap时说明要开始比较组里的第二个成员了//第二个成员比较完再比较第三个成员}else {break;}}arr[end gap] tmp;//有两种情况//1.end减少到 0说明这一组的数成倒序//则需要把组里所有的数比较并交换完之后结束循环//2.break提前跳出循环//说明此时组里所有比end位置大的数均位于end gap之后}}
}完
