鲜花网站有关建设,建设网站江西,阿森纳英超积分,手机门户网站建设方案文章目录 排序的稳定性插入排序插入排序的优化 希尔排序快速排序 排序的稳定性
稳定排序#xff1a;排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同。#xff08;比如#xff1a;冒泡、插入、基数、归并#xff09;
非稳定排序#xff1a;排… 文章目录 排序的稳定性插入排序插入排序的优化 希尔排序快速排序 排序的稳定性
稳定排序排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同。比如冒泡、插入、基数、归并
非稳定排序排序前2个数的相对位置在排序后会发生改变。比如选择、快速、希尔、堆等
插入排序
插入排序一般也被称为直接插入排序。对于少量元素的排序它是一个有效的算法。
插入排序是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增1的有序表。
在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动。
void Insertion_Sort(int a[], int len)
{//外层循环 - 插入数据量for (int i 1; i len; i){//内层循环 - 每一趟需要做的事情for (int j i - 1; j -1; j--){if (a[j]a[j 1]){int temp a[j];a[j] a[j 1];a[j 1] temp;}}}
}插入排序的优化
在下面函数中通过使用一个临时变量temp来保存当前需要插入的元素。外层循环通过对整个待排序序列进行遍历从第二个元素开始下标为1将当前元素保存在temp中。
然后内层循环从当前元素的前一个元素开始向前遍历直到找到合适的位置插入temp。在内层循环中如果当前遍历到的元素大于temp就将该元素后移一位给temp腾出位置。
内层循环结束后将temp插入到合适的位置即将其赋值给a[j1]这样就完成了一次元素的插入。
通过这种方式不断地将元素逐个地插入到已排序的序列中最终得到一个完全有序的序列。
void Insertion_Sort(int a[], int len)
{int temp, i, j;//外层循环 - 插入数据量for (i 1; i len; i){temp a[i];//内层循环 - 每一趟需要做的事情for (j i - 1; j -1 a[j] temp; j--){a[j 1] a[j];}//移动结束a[j 1] temp;}
}希尔排序
希尔排序Shell Sort是一种改进的插入排序算法也被称为“缩小增量排序”Diminishing Increment Sort。希尔排序通过将待排序序列分割成多个子序列来进行排序最终将这些子序列逐步合并为一个有序序列。
希尔排序的核心思想是通过定义一个增量序列也称为间隔序列将待排序序列划分成若干个子序列并对这些子序列分别进行插入排序。随着排序的进行增量序列会不断减小直到变为1此时对整个序列进行一次插入排序最终完成排序。
希尔排序的步骤如下 首先确定一个增量序列一般选择初始增量为序列长度的一半然后每次将增量折半直到增量变为1。 对每个增量进行插入排序即将待排序序列划分成若干个子序列对每个子序列进行插入排序。 在每次插入排序中按照增量的大小将元素分组对每组进行插入排序。 不断缩小增量重复步骤2和步骤3直到增量为1进行最后一次插入排序完成排序。
举个例子
如下图所示现有一序列8、5、7、3、6、1、2、8选择初始增量为序列长度的一般即初始增量为4分为四个组标红数字所示。 第一次交换组别增量为4 8和6为一组5和1为一组……队每组中的数比较排序例第一组排序8比6大则8、6互换位置以此类推排序后的结果如下图所示。 第二次交换组别增量由4变为2如下图所示。 先对1组进行比较首先6作为已序。第一次比较1组的第一个数6与第二个数2进行比较26小插入到6的位置6换到2的位置。第二次比较1组的第二个数6与第三个数8进行比较68则不进行插入。第三次比较1组的第三个数8与第4个数7进行比较87所以7插入到8的位置8换到7的位置。最终1组排序的结果如下 同理对2组进行比较后的结果如下图所示。 第三次交换组别增量从2变为1 组别增量变为1之后对整体做插入排序结果如下。
希尔排序函数
//希尔排序
void Shell_Sort(int a[], int len)
{int temp, i, j, n 0;//增量分组int jump len 1;while (jump ! 0){//外层循环 - 插入数据量for (i jump; i len; i){temp a[i];//内层循环for (j i - jump; j 0 a[j]temp; j - jump){a[j jump] a[j];n 1;}//移动结束a[j jump] temp;}//增量更新jump 1;}
}分别在优化后的插入排序函数和希尔排序中定义一个变量n用来统计各自进行数据交换的次数结果如下 插入排序交换的次数约是希尔排序交换次数的两倍
快速排序
快速排序Quicksort是对冒泡排序的一种改进。
快速排序的核心思想是通过分治法将一个大的待排序序列逐步地分割成小的子序列然后对这些子序列进行排序最终得到一个有序序列。具体步骤如下
选择一个基准元素pivot可以是序列中的任意一个元素。将序列分为两部分小于等于基准元素的部分和大于基准元素的部分。可以通过两个指针 i 和 j 来实现开始时 i 指向序列的第一个元素j 指向序列的最后一个元素。 从左向右找出第一个大于基准元素的元素记为 a。从右向左找出第一个小于等于基准元素的元素记为 b。如果 i j则交换 a 和 b 的位置然后继续找下一对 a 和 b。如果 i j则停止查找。 将基准元素与 j 所指向的元素交换位置即将基准元素放在合适的位置。递归地对基准元素左边和右边的子序列进行快速排序。
以下是一个使用 C 语言实现的快速排序代码示例
#include stdio.h// 交换两个元素的值
void swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}// 快速排序的递归函数
void quickSort(int arr[], int low, int high)
{if (low high) {int pivot arr[low]; // 选择第一个元素作为基准元素int i low, j high;while (i j){while (i j arr[j] pivot) {j--;}while (i j arr[i] pivot) {i;}if (i j) {swap(arr[i], arr[j]);}}swap(arr[low], arr[i]);quickSort(arr, low, i - 1); // 对左边子序列进行快速排序quickSort(arr, i 1, high); // 对右边子序列进行快速排序}
}// 打印数组元素
void printArray(int arr[], int size)
{for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}int main()
{int arr[] {8, 5, 7, 3, 6, 1, 2, 8};int size sizeof(arr) / sizeof(arr[0]);printf(原始数组);printArray(arr, size);quickSort(arr, 0, size - 1);printf(排序后数组);printArray(arr, size);return 0;
}输出结果 分析程序 代码首先定义了一个 swap 函数用于交换两个元素的值。然后quickSort 函数使用递归实现了快速排序的具体操作。最后在 main 函数中创建一个待排序的数组并调用 quickSort 函数对数组进行排序。最终通过调用 printArray 函数打印排序后的数组。
