给网站设置长尾关键词,山东省住房城乡建设部网站首页,网站建设品牌策划,商标设计用什么软件冒泡排序 冒泡排序时通过无序区中相邻记录的关键字间的比较和位置的交换#xff0c;使关键字最小的元素如气泡似的逐步上浮直水面。有序区逐渐扩大#xff0c;无序区逐渐缩小。 冒泡排序算法的原理如下#xff1a;
比较相邻的元素。如果第一个比第二个大#xff0c;就…冒泡排序 冒泡排序时通过无序区中相邻记录的关键字间的比较和位置的交换使关键字最小的元素如气泡似的逐步上浮直水面。有序区逐渐扩大无序区逐渐缩小。 冒泡排序算法的原理如下
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
动画演示 冒泡排序是一种非常容易理解的排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 普通冒泡
void bubble0(vectorint arr)
{int size arr.size();for(int i 0; i size; i) { for(int j 0; j size-i-1; j){if(arr[j] arr[j1]){swap(arr[j1], arr[j]);}}}
}优化一 第一种优化就是在交换的地方加一个标记如果某一趟排序没有交换元素说明这组数据已经有序不用再继续下去。这样对部分连续有序而整体无序的数据大大提升了效率。 void bubble1(vectorint arr)
{int size arr.size();for(int i 0; i size; i){ bool flag true;for(int j 0; j size-i-1; j){if(arr[j] arr[j1]){flag false;swap(arr[j1], arr[j]);}}if(flag)return;}
}优化二 对于优化一来说仅仅对部分连续有序而整体无序的数据效率高一些如果这组数据时前面无序但是后面的部分有序效率就不是那么高了。因此可以在优化一的基础上记下最后一次交换的位置这个位置后没有交换必然是有序的然后下一次排序从第一个比较到上次记录的位置结束即可。
void bubble2(vectorint arr)
{int size arr.size() -1;int pos size;for(int i 0; i size; i){bool flag true;int k 0;for(int j 0; j pos; j){if(arr[j1] arr[j]){flag false;swap(arr[j1], arr[j]);k j;}}if(flag)return;pos k;}
}优化三 冒泡算法经过优化二后效率有很大的提升但是效率还可以继续优化就是在一趟排序中确定两个最值也就是一个正向查找最大值另一个反向查找最小值
void bubble3(vectorint arr)
{int size arr.size() -1;int pos size;int pos1 0; for(int i 0; i size; i){bool flag true;int k 0; //正向冒最大值for(int j 0; j pos; j){if(arr[j1] arr[j]){flag false;swap(arr[j1], arr[j]);k j;}}if(flag)return;pos k;//反向冒最小值int n pos1;for(int j k; j pos1; --j){if(arr[j-1] arr[j]){swap(arr[j-1], arr[j]);n j-1;flag false;}}if(flag)return;pos1 n;}
}选择排序 选择排序是一种简单直观的排序算法。 选择排序原理
初始时设第一个元素为最大值并记录其下标为maxpos从剩余未排序元素中继续寻找最大元素如果当前元素比下标为maxpos的元素大将maxpos更新到当前位置一次遍历后将下标为maxpos的元素与最后一个元素交换位置以此类推直到整个数组有序。 注意选择排序与冒泡排序是区别的冒泡排序通过依次交换相邻两个顺序不合法的元素位置从而将当前最大元素放到合适的位置而选择排序每遍历一次都记住了当前最大元素的位置最后仅需一次交换操作即可将其放到合适的位置。 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 void slectSort(vectorint arr)
{int size arr.size();for (int i 0; i size - 1; i){int maxPos 0;for (int j 1; j size - i; j){if (arr[j] arr[maxPos])maxPos j;}if (maxPos ! size-i-1)swap(arr[maxPos], arr[size - i-1]);}
}优化 选择排序的优化就是在原来的一次只标记一个最值优化为一个标记两个最值这样效率可以提升原来的一半。
void SlectSort(vectorint arr)
{int size arr.size();int begin 0;int end size - 1;while (begin end){int minPos begin;int maxPos begin;int index begin 1;while (index end){if (arr[minPos] arr[index])minPos index;if (arr[maxPos] arr[index])maxPos index;index;}if (maxPos ! end)swap(arr[maxPos], arr[end]);//这段小代码在在下面介绍其作用if (minPos end)minPos maxPos;if (minPos ! begin)swap(arr[begin], arr[minPos]);begin;--end;}
} 上面代码标记的一小段代码是为了防止minpos在最大值要插入的位置。比如序列21541这时候的maxpos为1minpos为3调整过最大值后序列就成了21415这时候的minpos还是3如果直接进行最小值交换就恢复到之前的位置了所以要加上这段判断代码。这样如果最小值在最大值要交换的位置最大值交换后要将最小值的位置更新到maxpos的位置。
插入排序 直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想 当插入第i(i1)个元素时前面的arr[0],arr[1],…,arr[i-1]已经排好 序此时用arr[i]与arr[i-1],arr[i-2]进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。 元素集合越接近有序直接插入排序算法的时间效率越高其时间效率在O(n)与O(n^2)之间。直接插入排序的空间复杂度为O(1)它是一种稳定的排序算法。 元素集合越接近有序直接插入排序算法的时间效率越高 时间复杂度O(N^2) 空间复杂度O(1)它是一种稳定的排序算法 稳定性稳定 void InsertSort(vectorint arr)
{int size arr.size();for (int i 1; i size; i){//待插入元素int key arr[i];//找插入位置int end i - 1;while (end 0 arr[end] key){//向后搬移数据arr[end 1] arr[end];end--;}//开始插入arr[end 1] key;}
}优化 普通的插入排序就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列这样我们不用按顺序依次寻找插入点可以采用折半查找的方法来加快寻找插入点的速度。 折半插入排序算法是一种稳定的排序算法比普通插入算法明显减少了关键字之间比较的次数因此速度比直接插入排序算法快但记录移动的次数没有变所以折半插入排序算法的时间复杂度仍然为O(n^2)与直接插入排序算法相同。
void InsertSort1(vectorint arr)
{int size arr.size();for (int i 1; i size; i){//待插入元素int key arr[i];//找插入位置int right i - 1;int left 0;if(arr[right] key){while (left right ){int mid left((right-left)1);if(arr[mid] key)left mid1;elseright mid-1;}}//开始搬移数据int end i -1;while(end left){arr[end1] arr[end];--end;}//开始插入数据arr[end 1] key;}
}希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N^1.3 - N^2 稳定性不稳定 void ShellSort(vectorint arr)
{int size arr.size();int gap size;while (gap 0){gap gap / 3 1;for (int i gap; i size; i){//待插入元素int key arr[i];//找插入位置int end i - gap;while (end 0 arr[end] key){arr[end gap] arr[end];end - gap;}//开始插入arr[end gap] key;}if(gap 1)break;}
}快速排序 快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定 普通快排 普通快排就是将当前序列的最后一个值作为标志然后开始分割序列。
int Partion(vectorint arr, int left, int right)
{int key arr[right-1];int begin 0;int end right-1;while (begin end){while (begin end arr[begin] key)begin;while (begin end arr[end] key)end--;if (begin ! end)swap(arr[begin], arr[end]);}if (begin ! right - 1)swap(arr[begin], arr[right - 1]);return begin;
}优化一挖坑法 挖坑法的原理就是在左边找到不符合条件的元素时将这个元素放在end处这时候begin位置就成了一个“坑”在右边找到不符合条件的元素时将这个元素放到begin位置将之前的“坑”填好以此类推最后将标志key保存的值放在begin位置将最后一个“坑”填满。
int Partion1(vectorint arr, int left, int right)
{int end right - 1;int begin left;int key arr[right - 1];while (begin end){while (begin end arr[begin] key)begin;if (begin end){arr[end] arr[begin];end--;}while (begin end arr[end] key)end--;if (begin end){arr[begin] arr[end];begin;}}arr[begin] key;return begin;
}
//齐头并进法
int Partion2(vectorint arr, int left, int right)
{int key arr[right - 1];int cur left;int pre cur - 1;while (cur right){if (arr[cur] key pre ! cur){swap(arr[pre], arr[cur]);}cur;}if (pre ! right-1)swap(arr[pre], arr[right - 1]);return pre;
}
//三数取中法
int MidNum(vectorint arr,int left, int right)
{int mid left ((right - left) 1);if (arr[left] arr[right]){if (arr[mid] arr[left])mid left;if (arr[mid] arr[right])mid right;}else{if (arr[mid] arr[left])mid left;if (arr[mid] arr[right])mid right;}return mid;
}
int Partion3(vectorint arr, int left, int right)
{int end right - 1;int begin left;int mid MidNum(arr, left, end);swap(arr[mid], arr[right - 1]);int key arr[right - 1];while (begin end){while (begin end arr[begin] key)begin;if (begin end){arr[end] arr[begin];end--;}while (begin end arr[end] key)end--;if (begin end){arr[begin] arr[end];begin;}}arr[begin] key;return begin;
}
void QuickSort(vectorint arr, int left, int right)
{if (right - left 1){int key Partion3(arr, left, right);QuickSort(arr, left, key);QuickSort(arr, key 1, right);}
}
//非递归快排
void QuickSortNor(vectorint arr)
{int right arr.size();int left 0;stackint s;s.push(right);s.push(left);while (!s.empty()){left s.top();s.pop();right s.top();s.pop();if (right - left 1){int key Partion3(arr, left, right);//保存右值s.push(right);s.push(key 1);//保存左值s.push(key);s.push(left);}}}堆排序 堆排序就是利用堆堆的详细介绍这种数据结构进行排序的算法堆排序属于选择排序 时间复杂度O(nlogn) 空间复杂度O(1) 稳定性不稳定 堆排序的步骤为 1、基于所给元素创建一个大堆 2、使用堆删除的思想从最后一个结点向前调整 typedef struct Heap
{HPData* _array;int _size;int _capacity;
}Heap;void HeapAdjust(HPData* array, int size, int root)
{int child root * 2 1;while (child size){if (child 1 size array[child] array[child 1])child 1;if (array[child] array[root]){swap(array[child], array[root]);root child;child root * 2 1;}elsereturn;}
}void HeapSort(HPData* array, int size)
{//建大堆//找倒数第一个非叶子节点int root (size - 2) 1;for (; root 0; --root)HeapAdjust(array, size, root);//开始排序使用删除节点的思想int end size - 1;while (end){swap(array[0], array[end]);HeapAdjust(array, end, 0);end--;}
}归并排序 归并排序是简历在归并操作上的一中有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列。显示每个子序列有序再使子序列段间有序。若两个有序列表合并成一个有序列表陈伟二路归并。 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定 void _MergeData(vectorint arr, int left, int mid, int right, vectorint temp)
{int begin1 left;int end1 mid;int begin2 mid;int end2 right;int index left;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2])temp[index] arr[begin1];elsetemp[index] arr[begin2];} while (begin1 end1)temp[index] arr[begin1];while (begin2 end2)temp[index] arr[begin2];}void _MergeSort(vectorint arr, int left, int right, vectorint temp)
{if ((right - left) 1){int mid left ((right - left) 1);_MergeSort(arr, left, mid, temp);_MergeSort(arr, mid, right, temp);_MergeData(arr, left, mid, right, temp);copy(temp.begin() left, temp.begin() right, arr.begin() left);}
}
