用墨刀做网站后台原型,网站设计的尺寸,营销推广48个方法,小红书官方推广排序算法通常是针对数组或链表进行排序#xff0c;在C语言中#xff0c;需要手写排序算法完成对数据的排序#xff0c;排序规则通常为升序或降序#xff08;本文默认为升序#xff09;#xff0c;在C中#xff0c;algorithm头文件中已经封装了基于快排算法的 st…排序算法通常是针对数组或链表进行排序在C语言中需要手写排序算法完成对数据的排序排序规则通常为升序或降序本文默认为升序在C中algorithm头文件中已经封装了基于快排算法的 std::sort() 函数但是快速排序是不稳定的排序算法于是algorithm中还包含了 stable_sort() 函数即保留了等值元素的相对顺序。
稳定性通常在排序算法中稳定性是指如果两个元素在原始数组中的相对顺序保持不变则在排序后它们的相对顺序也应该保持不变。换句话说如果有两个相等的元素它们的位置在排序之前是 a 和 b且 a 在 b 的前面那么在排序后a 仍然应该在 b 的前面。
在进行排序算法之前先定义一个用于交换元素位置的函数
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
} 一、冒泡排序Bubble Sort
冒泡排序的核心算法是暴力求解思维是指将所有元素都相互比较一次若靠前的数比靠后的数大则将两个数交换位置。
排序对象数组时间复杂度空间复杂度是否稳定是
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i){for (int j 0; j n - i - 1; j){if (arr[j] arr[j 1]){Swap(arr[j], arr[j 1]);}}}
} 二、插入排序Insert Sort
插入排序的核心算法是将当前遍历到的地方的末尾数据往前比较找到合适的位置进行插入直到遍历到最后一个数据。
排序对象数组、链表时间复杂度空间复杂度是否稳定是
void InsertSort(int* arr, int n)
{int i 1;for (; i n; i){int j i;int end arr[j];while (j 0 arr[j - 1] end){arr[j] arr[j - 1];--j;}arr[j] end;}
} 三、选择排序Select Sort
选择排序的算法核心是找到数组的最大值和最小值将其和遍历数组的左右端进行交换然后左端右移、右端左移。简易版的选择排序算法会只找一个最值进行交换。
排序对象数组、链表时间复杂度空间复杂度是否稳定否
void SelectSort(int* arr, int n)
{int left 0;int right n - 1;while (left right){int iMin left; int iMax right;for (int i left; i right; i){if (arr[i] arr[iMin])iMin i;if (arr[i] arr[iMax])iMax i;} Swap(arr[left], arr[iMin]);if (left iMax)iMax iMin;Swap(arr[right], arr[iMax]);left;--right;}
}
