网站设计要素,青岛个人建站模板,海南网站开发,网站建设是什么行业1#xff09;排序思想#xff1a;
2#xff09;排序代码#xff1a;
3#xff09;注意点#xff1a;
4#xff09;时间/空间复杂度和稳定性 下面的排序是以实现升序讲解的。
#xff08;一#xff09;直接插入排序
1#xff09;排序思想#xff1a;
把待排序的…1排序思想
2排序代码
3注意点
4时间/空间复杂度和稳定性 下面的排序是以实现升序讲解的。
一直接插入排序
1排序思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列
2排序代码
void InsertSort(int* a, int n)
{for(int i 0;i n - 1;i){// 第一趟排序int end i;int temp a[end 1];while(end 0 temp a[end]){// 向后移动数据直到找到合适的位置a[end 1] a[end];end--;}// 找到合适的位置进行插入a[end 1] temp;} }
3注意点 a) 总趟排序的end小标的范围是[0, n-1]而不是[0, n], 因为如果是[0, n], temp a[end1]会造成越界访问; b) 在内部while循环的循环条件要保证end不能小于0因为当end减到-1时在进行a[end]会造成越界访问。
4时间/空间复杂度和稳定性
直接插入排序的时间复杂度当要排序的数据是逆序时时间复杂度为O(N^2); 当要排序数据是顺序的时时间复杂度为O(N)。
空间复杂度O(1).
稳定性 算法的稳定性指的是在排序算法中具有相同键值的元素在排序前后的相对位置是否保持不变。 在某些排序场景中可能存在相同键值的元素比如多个学生按照成绩进行排序。如果排序算法是稳定的那么具有相同成绩的学生就要以交卷时间进行排名花费时间少的排名高在排序后仍然保持原来的顺序并且排序后的结果是稳定的。 插入排序算法的基本思想是将待排序的元素逐个插入已排序部分的合适位置。在插入过程中如果存在相同键值的元素就会将新元素插入到已存在的元素之后从而保持相同键值元素的相对顺序不变。
所以插入排序算法是稳定的。 与冒泡排序的横向比较
冒泡排序是严格的n-1(n-2)(n-3)(n-4)……21无论数据是什么样子的。
而对于插入排序来说只有当数据是完全逆序是从前向后插入才是这么多次的比较次数12……(n-2)(n-1)如果插入数据时其前面已经是有序的或者有几个不是有序的那么这个数据就不需要进行完全的比较就可以确定其位置。例如1 2 3 4 中插入一个5就可以直接将5插入到该序列的后面就能保证数据是有序的或者是1 2 4 5中插入一个3只需要比较依次比较5 和 4两次后就能确定3的位置保证数据是有序的。
而如果对于 1 2 4 5 3使用冒泡排序的话就需要1 2和2 4 和4 5和5 3、1 2和2 4和4 3和4 5
这么多次比较才能将插入的3放到相应的位置。 二希尔排序
1排序思想
先选定一个整数作为分割距离把待排序文件中所有记录分成几个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当距离到达1时所有记录在统一组内排好序。
2排序代码
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap / 2;for (int i 0; i n - gap; i) // in,在第一趟时endin-1此时temp会越界{int end i;int temp a[end gap];if (temp a[end]){while (end 0 a[end] temp) {a[end gap] a[end];end - gap;}a[end gap] temp;}}}
}
3注意点
1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快最后一次排序的时间复杂度为O(N)。这样整体而言可以达到优化的效果。
这里的注意点和直接插入排序算法要注意的是一样的。直接插入排序的实现就相当于希尔排序算法的gap间距为1.
4时间/空间复杂度和稳定性
时间复杂度 空间复杂度O(1)
稳定性
在希尔排序的过程中相同键值的元素可能会因为间隔的不同而被分散到不同的分组中。当进行插入排序时不同分组内的元素会交替进行比较和移动这可能导致相同键值的元素之间的相对顺序发生变化。
因此由于希尔排序采用间隔分组的方式相同键值元素可能跨越不同的分组排序后的结果可能会改变相同键值元素的相对位置所以希尔排序是不稳定的。 这个分析方法是按照每次排序后数据还是逆序的进行分析。实际上效率会比下面的分析得到的结果高。 三选择排序
A. 直接选择排序
1排序思想
它的基本思想是每次从待排序序列中选择最小的元素将其放到序列的开头从排序序列中选择最大的元素将其放到序列的结尾。
2排序代码
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin, mini begin;// 找到最大值和最小值的下标for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}// 交换Swap(a[maxi], a[end]);// 如果最小值在序列结尾将最大值与最小值交换后最小值已经不在序列结尾处了// 所以要记录下最小值的位置if (mini end){mini maxi;}Swap(a[mini], a[begin]);begin;end--;}
}
3注意点
一要注意更新每一次最大值和最小值以便能够找到正确的最大值和最小值
二要注意最大值放到序列最后时可能会导致最小值的下标指向的不再是最小值。
4时间/空间复杂度和稳定性
时间复杂度选择排序的外层循环执行了 n-1 次内层循环在最坏情况下需要执行 (n-1) (n-2) ... 1 n(n-1)/2 次比较操作。同时每次外层循环还需要进行两次元素交换操作。 因此整个选择排序的时间复杂度为 O(n^2)。
空间复杂度选择排序只需要使用常数级别的额外空间用于存储临时变量因此空间复杂度为 O(1)。
稳定性
稳定性分析 如果序列中存在相同键值的元素并且该值是最大值在从前向后寻找最大值时会选择前面一个值作为最大值并交换到本次序列的最后在第二次寻找最大值时会选择这个相等的值并放到本次序列的最后但是本次序列的最后是上一次序列最后的前一个在排序完成后它们的相对位置发生变化导致算法不稳定。所以直接选择排序是不稳定的。 选择排序是一种简单的排序算法它的基本思想是每次从未排序部分选择最小或最大的元素放到已排序部分的末尾。在对长度为n的数组进行选择排序时需要进行n-1轮比较和交换。 在第一轮比较中需要将第一个元素与后面n-1个元素进行比较共需要n-1次比较。 在第二轮比较中需要将第二个元素与后面n-2个元素进行比较共需要n-2次比较。 以此类推最后一轮比较只需要将倒数第二个元素与最后一个元素进行比较共需要1次比较。 因此总的比较次数可以计算为(n-1) (n-2) ... 2 1 n(n-1)/2。 对于长度为100的数组进行选择排序比较的次数为100(100-1)/2 4950次。 B. 堆排序
1排序思想
用向下调整法建一个大堆将根节点和最后一个节点进行交换然后再对根节点进行向下调整使新的根节点到达合适的位置。每完成一次排序堆的节点个数减一以此类推直到堆的节点个数为1的时候完成排序。
2排序代码
// 向下调整法
void AdjustDwon(int* a, int n, int root)
{int child root * 2 1;while (child n){// 找到较大的孩子节点if (child 1 n a[child] a[child 1]){child;}if (a[root] a[child]){// 交换Swap(a[root], a[child]);root child;child root * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 利用大堆实现升序// 使用向下调整法将数组调整成为大堆int end n - 1; // 最后一个叶子节点的下标for (int i (end - 1) / 2; i 0; i--){AdjustDwon(a, n, i);}// 排序// 根节点与最后一个节点交换根节点向下调整堆的数据量减一直到堆的数据量为0时结束排序while (end 0){Swap(a[0], a[end]);AdjustDwon(a, end, 0);end--;}
}
3注意点
注意向下调整的实现方法。
4时间/空间复杂度和稳定性
时间复杂度O(N*logN)
空间复杂度O(1)
稳定性
使用向下调整时如果一个节点的两个孩纸节点的值相同的并且为最大值我们默认实现的是左孩子结点与其父节点进行交换最终这个左孩子结点会被交换到根节点的位置然后进行根节点和最后一个叶子节点进行交换堆的节点数减一第二次进行向下调整时右孩子节点为最大值会被移动到根节点然后再与本次最后一个叶子节点进行交换但此时最后一个叶子节点是上一次排序的最后一个叶子节点的前一个。起初这两个节点的顺序是AB 最大值但排序过后的顺序变成BA 最大值。
所以堆排序是不稳定的。
四交换排序
A. 冒泡排序法
1排序思想
它的基本思想是比较相邻的元素如果前面的元素大于后面的元素则将它们互换位置。重复进行这个过程直到不能再交换为止。
具体来说冒泡排序的过程如下 依次比较相邻的元素如果前面的元素大于后面的元素则将它们互换位置。 对所有相邻的元素进行一次遍历后最后一个元素一定是当前未排序部分中最大的元素。 对剩余的元素继续进行第1、2步操作直到整个序列有序为止。
2排序代码
void Swap(int* x, int* y)
{int temp *x;*x *y;*y temp;
}void BubbleSort(int* a, int n)
{// 整趟排序逻辑for (int i 0; i n - 1; i){// 一趟排序int Isexchange 0;for (int j 1; j n - i;j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);Isexchange 1;}}if (Isexchange 0) // 如果没有发生交换则说明数组已经是有序的了此时不需要再进行下去了{break;}}
}3注意点
内部循环的范围第一次范围是[1, n-1]此时最后一个数已经到最后要到的位置第二次排序不需要再对最后一个数进行排序所以第二次范围是[1, n-1-1]……
4时间/空间复杂度和稳定性
时间复杂度O(N^2) 空间复杂度O(1) 稳定性相同键值的元素不会发生交换所以在排序前后两者相对位置不会发生变化所以冒泡排序算法是稳定的。
B. 快速排序
1排序思想
任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
一趟排序逻辑key左边的值小于keykey右边的值大于key--最终左右序列中间中间部分就是key值排序完成的位置。就相当于一次单趟排序将基准值移动到其最终的位置。 当右边指针先移动时 左右指针在找大和找小过程中最终相遇位置一定是比key值小的
如果右指针先走最终相遇前有两种情况
a) R动L不动R与L相遇在L的位置上
bL动R不动L与R相遇在R的位置上。
aR先走左边没有比key值小的就一直向左移动直到与L指针相遇而由于上一轮L和R交换后R值是小于key值的L指针指向的值就是小于key值的 b) R先走找到小于key的值后停下来接着L向后走直到找到大于key的值或与R相遇而R最后停下的地方就是小于key值的。 这里补充一下如果是实现降序那就是左边找小右边找大。
先让左边先走还是先让右边先走却决于key值的位置如果key值在左边那就让右边先后如果key值在右边那就让左边先走。
总之就是让key对面的指针先走才能保证两指针相遇的位置是小于key值的。
2排序代码
// 单趟排序
int PartSort1(int* a, int left, int right)
{int keyi left;while (left right){// 左边找大while (left right a[left] a[keyi]){left;}// 右边找小while (left right a[right] a[keyi]){right--;}}Swap(a[keyi], a[left]);return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}3注意点
hoare单趟排序
a) 要求右指针先进行找小在进行左指针找大保证两者相遇位置的值小于key值
b) 如果条件只是 大于或小于 key值找小和找大过程中可能会死循环当找大/找小过程中有值等于key值会跳出找大和找小循环然后进行交换再回到外层循环判断条件beginend循环继续进入内部由于当前值等于key值所以不会进入内部循环会再次进行交换、外部条件判断……最后死循环
c) 也可能会找不到小于key值和大于key值导致越界
d) 递归结束条件最后的情况是有一组两个数的数组一个是key另一个要么在key的左边左边进行递归的参数为beginkey-1begin等于key-1右边进行递归的参数为key1key该范围不存在要么在key的右边那么其左边的范围不存在右边范围两端点相等。
4时间/空间复杂度和稳定性
时间复杂度O(N^logN)
空间复杂度O(1)
稳定性如果待排序序列中存在相同关键字的元素而它们在划分过程中被放置到不同的子序列中那么它们的相对顺序就会改变导致不稳定性。所以快速排序是不稳定的
5对hoare快速排序的优化 在数据理想的情况下如果每次选取的key值最终位置都在序列的中间那么时间复杂度为O(N^logN);
但如果数据接近有序的情况下需要进行N次排序才能保证排序完成最终时间复杂度为O(N^2);
a) 优化方案一三数取中
避免上图的第二种情况key值在最左边尽量保证key值最终在两序列的中间
如何实现呢 我们发现当key值的大小接近最大值和最小值的中间值时那么最终数据被分为左右序列时左右序列的数据个数会比较平均这样最后交换后key值最终就尽可能处于中间位置了。
而出现第二种情况的原因是数据基本已经接近有序了这也就意味着序列中间位置的值接近中间值所以可以选择中间位置的值作为key值。
但是如果选择中间位置的值作为key值后在进行单趟排序时还要确定左右指针先走还是后走问题为了不改变单趟排序的逻辑我们可以将中间位置的值与最左边的值交换。
但是又不能对于所有将要排序的序列都交换中间值要记住交换仅仅是为了应对数据接近有序这种极端情况。
所以我们可以选择三个数中的中间值下标与左边交换这样既能够应对极端情况还能不影响普通情况。
int Getmidi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}elsereturn left;}else //a[mid] a[left]{if (a[right] a[mid]){return mid;}else if (a[left] a[right]){return right;}elsereturn left;}
}int midi Getmidi(a, left, right);Swap(a[left], a[midi]);
注意
三数取中法的快速排序并不总是在任何情况下都是速度最快的排序方式。
快速排序的时间复杂度是平均情况下最好的但在某些特殊情况下例如已经有序或者逆序的序列快速排序的性能会下降。三数取中法是一种优化手段用于尽量避免这种情况。
三数取中法选择首、尾和正中三个数进行取中选取它们的中间值作为基准值。这样可以有效避免快排单链的情况尤其对已经有序的序列的速度改善明显。
但是仍然存在一些特殊序列比如大量重复元素的序列三数取中法也无法完全解决 每次划分操作的时间复杂度是O(n) 的情况并且需要执行n次划分操作。这样总的时间复杂度将是O(n * n)即O(n^2)。 b挖空法
由于hoare这种方法需要考虑左右指针先走问题我们可以对这个进行改进
当我们选取key值后就在key值位置形成一个坑这样就自然而然地让右面先走找到一个值填到这个坑中右边的值填过去后右边就会形成一个新的坑接着让左边找值填坑。
int PartSort2(int* a, int left, int right)
{int midi Getmidi(a, left, right);Swap(a[left], a[midi]);int key a[left];int hole left;while (left right){while (left right a[right] a[hole]){right--;}a[hole] a[right];hole right;while (left right a[left] a[hole]){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
所以挖坑法并不是对快速排序进行优化而是让我们实现快速排序时逻辑更简单。
c前后指针法
使用前后指针法会更容易实现快速排序。 主要思想是实现升序让cur找小于key的值prev交换prev和cur的值。
在移动过程中prev和cur的位置会有两种情况
1. prev相邻当cur找到小于key的值时prev后交换相当于自己跟自己交换
2. 当cur遇到大于key值时cur和prev会拉开距离当cur再次找到小于key值时两指针中间的数值都是大于key值的prevprev指向大于key的值交换后大于key的值被放到后面小于key的值被放到前面。本质类似于推箱子将大于key的区间推到后面小于key的区间推到前面
3. 当cur移动到数组之外时prev指向小于key的值
int PartSort3(int* a, int left, int right)
{int midi Getmidi(a, left, right);Swap(a[left], a[midi]);int keyi left;int pre left;int cur pre 1;while (cur right){if (a[cur] a[keyi] pre ! cur) //尽量用这种方式{Swap(a[cur], a[pre]);}cur;}Swap(a[keyi], a[pre]);return pre;
}
d) 递归深度的优化
由二叉树的知识可以知道最后几层的节点个数占据整个树节点的大多数所以对于后面几层的节点在使用快速排序递归消耗会比较大我们可以使用插入排序进行排序减少递归的消耗。
void QuickSort(int* a, int begin, int end)
{if (begin end) return;if ((begin - end 1) 10){int key PartSort3(a, begin, end);//第一趟排序QuickSort(a, begin, key - 1);//左边递归排序QuickSort(a, key 1, end);//右边递归排序}else{InsertSort(a begin, end - begin 1);}
}
6非递归实现快速排序 在使用递归算法时也存在一些消耗包括 1.内存消耗递归算法需要使用系统栈空间来保存函数的执行现场和局部变量等信息当递归深度较大时占用的栈空间也会随之增加。如果递归深度过大可能会导致栈溢出的异常从而使程序崩溃。 2.时间消耗递归算法一般需要进行多次函数调用而函数调用的过程涉及到参数传递、现场保存和恢复等操作这些操作都会耗费一定的时间。此外在某些情况下递归算法还可能存在重复计算的问题造成额外的时间消耗。 3.维护复杂度递归算法通常需要维护递归深度、参数传递等复杂度增加了程序的复杂度和维护难度。 为了消除递归的消耗我们可以用其他方法来模拟递归过程。
模拟实现递归的方法基本上有两种一是用栈模拟而是用循环模拟。
快排的思想是第一次将key值移动到正确位置并以key值位置将序列分割为两个序列然后再对这两个序列进行key值的移动---这个过程类似于二叉树的前序遍历可以用栈进行模拟实现。
入栈要保存的数据是要进行单趟排序的范围。
具体过程如下
先将数据的起始位置压入栈中然后出栈得到第一次要进行排序的范围进行第一次单趟排序第一次排序结束后key位置将序列分为两个部分[left, key-1] 和 [key1, right]判断这两个范围是否合法合法将这两个范围压入栈中不合法范围不存在 或左右端点相等就不需要再排序了之后出栈得到第二次排序的范围进行第二次单趟排序的范围重复上述过程直到栈为空时排序完成
void QuickSortNonR(int* a, int left, int right)
{// 创建栈Stack stack;StackInit(stack);StackPush(stack, right);StackPush(stack, left);while (!StackEmpty(stack)){int begin StackTop(stack);StackPop(stack);int end StackTop(stack);StackPop(stack);// 单趟排序int keyi PartSort1(a, begin, end);// 右数组入栈if (keyi 1 end){StackPush(stack, end);StackPush(stack, keyi 1);}// 左数组入栈if (begin keyi - 1){StackPush(stack, keyi - 1);StackPush(stack, begin);}}StackDestroy(stack);
}
