网站开发外包 价格,wordpress 访问控制,浪起网站建设,福清市建设局监督站网站前言#xff1a;生活中我们总是会碰到各种各样的排序#xff0c;今天我们就对部分常用的排序进行总结和学习#xff0c;今天的内容还是相对比较简单的一部分#xff0c;各位一起加油哦#xff01; #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x1f49e; #x1f44…前言生活中我们总是会碰到各种各样的排序今天我们就对部分常用的排序进行总结和学习今天的内容还是相对比较简单的一部分各位一起加油哦 博主CSDN主页:卫卫卫的个人主页 专栏分类:数据结构 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 插入排序
插入排序我们可以通俗的理解成将一个数记录下来按其数值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。(由于动图画的实在太过于繁琐博主就画了一半请见谅)
代码思路由此图我们可以知道我们用一个tmp记录后面一个元素如果后面的比前面的小就让前面的元素逐一和他比较并往后走如果碰到比他小的就停下来插入到此位置。不理解的话可以理解成我们平常玩的斗地主的牌拿一张牌插到应该有的位置。 代码实现
void InsertSort(int* a, int n)//插入排序
{for (int i 0; i n - 1; i)//升序{int end i;int tmp a[end 1];//保存后一个while (end 0){if (tmp a[end])//前一个大于后一个,让大的全部往后走{a[end 1] a[end];end--;}else{break; }}a[end 1] tmp;//在把小的放在此时的位置}
}测试函数:
void Test_InsertSort()
{int a[] { 1,2,30,0,99,1,7,8,2,11,0,3,13 };InsertSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}排序结果: 希尔排序
希尔排序:我们可以通俗的把待排的序列看成若干个子序列然后对其分别进行直接插入排序最后在对全部进行一次排序即可。(如下图所示) 我们可以理解成gap1是预排序目的是让它接近有序 gap 1是直接插入排序目的是让它有序。但是记住最后一定要让gap最后一次排序为1。 代码思路:我们可以把每次排序写成一次插入排序然后最后一让其间距不断的变化直到最后一次全部排序完成。 代码实现:
void ShellSort(int* a, int n)//希尔排序
{int gap n;while (gap){gap gap / 2 ;for (int i 0; i n - gap; i)//升序{int end i;int tmp a[end gap];//保存后一个while (end 0){if (tmp a[end])//前一个大于后一个,让大的全部往后走{a[end gap] a[end];end end -gap;}else{break;}}a[end gap] tmp;//在把小的放在此时的位置}}
} 函数测试
void Test_ShellSort()
{int a[] { 1,2,30,0,99,1,7,8,2,11,0,3,13 };ShellSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}运行结果: 冒泡排序
冒泡排序也是我们所碰到的最简单的一种排序这种排序的思想是十分简单的我们可以理解成每一趟找到序列中最大的一个或最小的元素排序到序列的最左边(右边)然后排序序列的有效次数趟即可排序完成(如下图)。
代码实现:
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void BubbleSort(int* a, int n)//冒泡排序
{int i 0;for (int j 0; j n - 1; j){for (i 0; i n - j -1; i)//每一趟找到一个最大的{if (a[i] a[i 1]){Swap(a[i], a[i 1]);}}}
} 函数测试:
void Test_BubbleSort()
{int a[] { 1,2,30,0,99,1,7,8,2,11,0,3,13 };BubbleSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}运行结果 选择排序
选择排序我们现在一组有序序列中找到最大(最小)和第一个位置交换然后再找次大的和第二个交换以此类推最后我们即可得到一个有序序列。如下图所示 代码实现
void SelectSort(int*a ,int n)//选择排序
{//现在数组中找到最小的然后和第一个位置交换//再找到次小的和第二个位置交换int min 0;for (int i 0; i n - 1 ; i){min i;//最小的数的下标for (int j i; j n; j){if (a[min] a[j])//找到最小位置的下标{min j;}}if(min ! i)Swap(a[i], a[min]);}
} 测试函数
void Test_SelectSort()
{//int a[] { 1,2,30,0,99,1,7,8,2,11,0,3,13 };int a[] { 1,0,0,0,99,1,7,8,2,9,0,3,0 };SelectSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));}运行结果: 但是上面这种方法我们一共要找n-1次我们思考一下每一次查找的过程中如果我们每次一起查找最大的和最小的那我们不就提高了一倍的效率。所以我们只需要再引入一个max变量来帮助我们再记录一下这个值即可。 代码实现
void SelectSort_best(int* a, int n)//选择排序
{int begin 0;int end n - 1;while (begin end){int max begin;int min begin;int i 0;for (i begin 1; i end; i)//找最小的和最大的{if (a[i] a[min]){min i;}if (a[i] a[max]){max i;}}Swap(a[begin], a[min]);if (begin max)//防止最大的和最小的是相同的{max min;}Swap(a[end], a[max]);begin;end--;}
}运行结果依然和前面的相同这里就不做更多的阐述了。 堆排序
堆排序前面我们讲了堆的模拟实现我们知道堆的父亲结点一定比它的孩子结点大(小)因此我们可以充分的利用这一点来进行排序。
首先我们们将数组中的元素想象成一个堆将其中的父亲结点全部向下调整。如下图根据我们模拟建立的大堆或者小堆将其堆顶元素和堆尾进行交换因此我们可以得到一个最大(最小的元素)再堆底然后再通过一个end记录尾部交换一次减减一次以此循环到end为0的时候即堆中所有元素也排序完成。(如下图所示) 代码实现:
void AdjustDown(int* a, int size, int parent)//向下调整
{assert(a);int child parent * 2 1;//找到第一个孩子while (child size){//看俩个孩子谁更小交小的那个与父亲去比较if (a[child] a[child 1] (child 1) size){child 1;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;//让父亲和儿子往下走child child * 2 1;}else{break;}}
}void HeapSort(int* a, int n)//堆排序
{int i 0;for (i (n - 1 - 1) / 2; i 0; i--)//建堆,只有父亲结点需要调整{AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}函数测试: void Test_HeapSort()
{int a[] { 20,10,8,2,1,2,7 };HeapSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));
}
运行结果: 好啦今天的内容就到这里啦下期内容预告【快速排序的模拟实现】-- 四种方式 结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 祝各位接下来好运连连
