分布式网站架构,外贸网站产品,竞价sem托管公司,江西网站开发软件公司目录 1. 各种排序算法的分类2. 插入排序2.1 直接插入排序2.2 希尔排序 3. 选择排序3.1 选择排序3.2 堆排序4. 交换排序4.1 冒泡排序4.2 快速排序4.2.1 霍尔法#xff08;hoare#xff09;4.2.2 挖坑法#xff08;hole#xff09;4.4.3 前后指针法4.4.4 补充#xff1a;非递… 目录 1. 各种排序算法的分类2. 插入排序2.1 直接插入排序2.2 希尔排序 3. 选择排序3.1 选择排序3.2 堆排序4. 交换排序4.1 冒泡排序4.2 快速排序4.2.1 霍尔法hoare4.2.2 挖坑法hole4.4.3 前后指针法4.4.4 补充非递归快排4.5 快排优化 5. 归并排序6. 非比较排序计数排序7. 排序算法的稳定性 1. 各种排序算法的分类 按照排序逻辑的不同排序大体可以分为四大类 插入排序选择排序交换排序归并排序 接下来我们进行这些排序的学习 注本章内容中的动图并非原创 2. 插入排序
2.1 直接插入排序 将整个数组的元素从起始遍历一次向后移动一步看作是将一个元素插入到数组中。在插入的过程中当新插入的元素小于其前面的元素时交换两者循环此步骤直至前面的元素不小于新插入的元素到此成功插入一个元素。 过程演示
void InsertSort(int* a, int n)
{for (int i 1; i n; i){for (int j i; a[j - 1] a[j]; j--){swap(a[j - 1], a[j]);}}
}2.2 希尔排序 根据给定组距进行数据的分组组内进行插入排序。不断减小组距直至组距为1。注在组距不为1时都是预排序让数据更接近有序。 //多趟排
void ShellSort1(int* a, int n)
{int gap n / 2;while (gap 0){for (int i 0; i gap; i){for (int j i; j gap n; j gap){if (a[j] a[j gap]){swap(a[j], a[j gap]);}}}gap / 2;}
}//一趟排
void ShellSort2(int* a, int n)
{int gap n / 2;while (gap 0){for (int i 0; i gap n; i){if (a[i] a[i gap]){swap(a[i], a[i gap]);}}gap / 2;}
}3. 选择排序
3.1 选择排序 遍历一次从数据中选出最小或最大的数据放至数据首部。多次遍历选择直至将最后一个数据选走。 过程演示
void SelectSort(int* a, int n)
{for (int i 0; i n; i){int min i;for (int j i; j n; j){if (a[j] a[min]){min j;}}swap(a[i], a[min]);}
}选择排序优化 一次遍历选出最大值与最小值 void SelectSort2(int* a, int n)
{for (int i 0; i n / 2; i){int max i;int min i;for (int j i; j n - i; j){if (a[j] a[max]){max j;}if (a[j] a[min]){min j;}}swap(a[max], a[n - i - 1]);swap(a[min], a[i]);}
}3.2 堆排序 建大堆交换首尾size–向下调整直到size为0 void AdjustDown(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;}
}void HeapSort(int* a, int n)
{//建大堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//交换首尾调整int size n;while (size 0){swap(a[0], a[size - 1]);size--;AdjustDown(a, size, 0);}
}4. 交换排序
4.1 冒泡排序 建立两个一前一后的指针用这两个指针遍历整个数组若后指针指向的数据大于前指针指向的数据交换前后指针所指向的元素之后两指针直至遍历完数据得出一个最大数需遍历的数据长度减1此为遍历一趟。多次遍历当长度为0时排序结束 过程演示
void BubbleSort(int* arr, int n)
{for (int i 0; i n; i){int flag 1;for (int j 0; j 1 n - i; j){if (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);flag 0;}}if (flag){break;}}
}4.2 快速排序
4.2.1 霍尔法hoare 将数据的首位确定为对照key定义两个指针left数据首部right数据尾部。右侧指针反向遍历数组寻找小于key的值当找到后停止左侧指针正向遍历数组寻找大于key的值找到后将两指针指向的数据交换。重复上述步骤2直至左右指针相遇交换key元素与左右指针同时指向的元素此为一趟排序。将数据分割为[0key - 1]与[key 1n]在这两个区间内再进行上述步骤23。直至所有元素的位置都被确认。 过程演示
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int key left;int keyi a[key];while (left right){while (left right a[right] keyi){right--;}while (left right a[left] keyi){left;}swap(a[left], a[right]);}if (a[left] keyi){swap(a[left], a[key]);key left;}return key;
}4.2.2 挖坑法hole 选择首位数据为key然后将数据的首位标记为hole创建两个指针left首位 right数据尾部。右侧指针找寻找小于key元素的值找到后将所找到的元素填充至挖好的洞里此元素原位置标记为新的洞然后移动左侧指针寻找大于key元素的值找到后将找到的元素填入洞中。重复上述步骤直至左右指针相遇将key值填入左右指针相遇的位置此时即确定好了key的位置。在[leftkey - 1]与[key 1, right]的区间中重复步骤2直至所有位置都被确定。 过程演示 int PartSort2(int* a, int left, int right)
{int hole left;int keyi a[hole];while (left right){//额外检查越界可能while (left right a[right] keyi){right--;}if (a[right] keyi){a[hole] a[right];hole right;}while (left right a[left] keyi){left;}if (a[left] keyi){a[hole] a[left];hole left;}}a[hole] keyi;return hole;
}void QuickSort(int* a, int left, int right)
{if (left right){return;}int key PartSort2(a, left, right);QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}4.4.3 前后指针法
思路1 将数据首位设置为key创建两个指针pre首部cur首部 1。cur开始遍历整个数组如果cur指针指向的值小于key那么pre指针一同否则pre指针不动直至cur再次寻找到小于key的值此时pre然后将两指针指向的值交换。如此反复直至cur遍历完整个数组最后将key与pre指针指向的值交换。在[leftkey - 1]与[key 1, right]的区间中重复步骤2直至所有位置都被确定。 思路2 [left 1pre]区间为小于key的值[pre 1cur - 1]为大于key的值[curright]为未遍历到的值。cur指针遍历寻找小于pre指针的数据找到后pre交换两指针所指向的值。 过程演示
int PartSort3(int* a, int left, int right)
{int pre left;int cur left 1;int keyi a[left];while (cur right){if (a[cur] keyi){swap(a[pre], a[cur]);}cur;}swap(a[left], a[pre]);return pre;
}void QuickSort(int* a, int left, int right)
{if (left right){return;}int key PartSort3(a, left, right);QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}4.4.4 补充非递归快排 将原本递归传递的区间存储到栈中用时从栈中取出 void QuickSortNonR(int* a, int left, int right)
{Stack stack;StackInit(stack);//插入第一次遍历区间范围StackPush(stack, left);StackPush(stack, right);while (!StackEmpty(stack)){//取出区间值进行运算right StackTop(stack);StackPop(stack);left StackTop(stack);StackPop(stack);int key PartSort3(a, left, right);//区间遍历顺序左区间右区间if (key 1 right){StackPush(stack, key 1);StackPush(stack, right);}if (left key - 1){StackPush(stack, left);StackPush(stack, key - 1);}}
}4.5 快排优化 三数取中getmid当递归到小区间时可以转而进行插入排序 //三数取中
int GetMidNum(int* a, int left, int right)
{int mid (left right) / 2;if(a[mid] a[left]){if(a[mid] a[right]){return mid;}else{if(a[right] a[left]){return right;}else{return left;}}}else{if(a[mid] a[right]){return mid;}else{if(a[left] a[right]){return left;}else{return right;}}}
}5. 归并排序
思路1 归并逻辑二叉树的遍历深度优先左右根 将需要进行归并的区间范围视作结点根结点的区间为整个数组左右孩子结点为将区间范围一分为2左孩子为前半区间右孩子为后半区间对每次得到的新区间都进行上述处理直至区间中的元素数2即视为叶子结点。按照后序遍历二叉树的顺序对结点区间内的数据进行插入排序。 过程演示 递归法
void _mergesort(int* a, int* tmp, int left, int right)
{//深度优先if (left right){return;}int mid (right left) / 2;_mergesort(a, tmp, left, mid);_mergesort(a, tmp, mid 1, right);//插入int i left;int j mid 1;int k left;while (i mid j right){//当存在相同的数时if (a[i] a[j]){tmp[k] a[i];}else{tmp[k] a[j];}}while (i mid){tmp[k] a[i];}while (j right){tmp[k] a[j];}memcpy(a left, tmp left, (right - left 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(n * sizeof(int));_mergesort(a, tmp, 0, n - 1);free(tmp);
}思路2 将数组的元素分为两个两个一组将每一组都使用插入排序调整为有序遍历一遍数组将一组中的元素数翻倍重复步骤1遍历完成再次翻倍直至一组中的元素数包含整个数组排序完成当剩余元素不足一组时将剩余元素也算作一组 非递归法
void MergeSortNonR(int* a, int n)
{int* c_a (int*)malloc(n * sizeof(int));int gap 1;while (gap n){//确定初始区间int begin1 0;int end1 begin1 gap - 1;int begin2 end1 1;int end2 begin2 gap - 1;//检测防止越界if (end2 n){end2 n - 1;}while (begin1 n){//插入int i begin1;int j begin2;int k begin1;while (i end1 j end2){if (a[i] a[j]){c_a[k] a[i];}else{c_a[k] a[j];}}while (i end1){c_a[k] a[i];}while (j end2){c_a[k] a[j];}//拷贝回原数组memcpy(a begin1, c_a begin1, (end2 - begin1 1) * sizeof(int));//向后调整区间begin1 end2 1;end1 begin1 gap - 1;begin2 end1 1;end2 begin2 gap - 1;//判断是否越界if (end1 n){end1 n - 1;}if (end1 n end2 n){end2 n - 1;}}gap * 2;}free(c_a);
}优化
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(n * sizeof(int));//确定间距int gap 1;while (gap n){//i中间记录for (int i 0; i n; i 2 * gap){int begin1 i;int end1 begin1 gap - 1;int begin2 end1 1;int end2 begin2 gap - 1;//上一趟已经遍历过if (end1 n){break;}if (end2 n){end2 n - 1;}int index begin1;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[index] arr[begin1];}else{tmp[index] arr[begin2];}}while (begin1 end1){tmp[index] arr[begin1];}while (begin2 end2){tmp[index] arr[begin2];}memcpy(arr i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}
}6. 非比较排序计数排序 根据数据的范围创建一个合适大小的数组。下标对应数据根据数据中各个数字的出现次数在对应的下标处计数。限制 1 数据范围不可跨度太大会导致空间复杂度过高 2只能用来处理整形数据。 过程演示
void CountSort(int* a, int n)
{//选出最大值与最小值int min a[0];int max a[0];for (int i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}//开辟空间int size max - min 1;int* count (int*)malloc(size * sizeof(int));memset(count, 0, n * sizeof(int));//计数for (int i 0; i n; i){count[a[i] - min];}//读数int index 0;for (int i 0; i size; i){while (count[i]){a[index] i min;count[i]--;}}
}7. 排序算法的稳定性 算法稳定性的判断标准数据中相同数据在排序后他们的相对位置是否变化。 直接插入排序稳定时间复杂度O( n 2 n^2 n2)希尔排序不稳定时间复杂度略小于O( n 2 n^2 n2)选择排序稳定O( n 2 n^2 n2)堆排序不稳定O( n n n * logn)冒泡排序稳定O( n 2 n^2 n2)快速排序不稳定O( n n n * logn)归并排序不稳定O( n n n * logn)计数排序稳定O(nMax)
