建设企业网站就等于开展网络营销,wordpress 首页置顶,网站怎么备案在哪里,wordpress 耗费内存目录 ♫什么是排序 ♪排序的概念 ♪排序的稳定性 ♪排序的分类 ♪常见的排序算法 ♫直接插入排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫希尔排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫直接选择排序 ♪基本思想 ♪算法… 目录 ♫什么是排序 ♪排序的概念 ♪排序的稳定性 ♪排序的分类 ♪常见的排序算法 ♫直接插入排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫希尔排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫直接选择排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫堆排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫冒泡排序 ♪基本思想 ♪算法实现 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫快速排序 ♪基本思想 ♪算法实现 ♪算法的优化 ♪算法稳定性 ♪时间复杂度 ♪空间复杂度 ♫归并排序 ♪基本思想 ♪算法实现 ♪算法的稳定性 ♪时间复杂度 ♪空间复杂度 ♫排序算法的比较 ♫什么是排序 ♪排序的概念 排序是将一组数据按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 ♪排序的稳定性 将一组数据进行排序后如果原数据与排序后的数据中相同元素的相对位置仍然保持不变那么该排序就是一个稳定的排序否则就不是一个稳定的排序。 注一个本身稳定的排序可以通过不稳定的算法实现而一个不稳定的排序是不能通过稳定的算法实现的。 ♪排序的分类 排序分为内部排序和外部排序两种 1. 内部排序数据元素全部放在内存中的排序。 2. 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序 ♪常见的排序算法 常见的排序算法有插入排序直接插入排序、希尔排序选择排序直接选择排序、堆排序交换排序冒泡排序、快速排序归并排序等这些排序算法也是我们接下来以从小到大排序为例重点要了解的东西。 ♫直接插入排序 ♪基本思想 直接插入排序是一种简单的插入排序算法它的基本思想是从第二个元素开始每个元素都往前找合适的位置插入直到所有的记录插入完为止就能得到一个有序序列。 ♪算法实现 //直接插入排序从小到大public void insertSort(int[] arr) {//空数组不用排if (arr null) {return;}//从第二个数开始到最后一个数for (int i 1; i arr.length; i) {//将待插入的数拿出来int tmp arr[i];int j 0;//从后往前找合适的插入位置待插入值比j位置的值大的位置的后面for (j i - 1; j 0; j--) {//判断待插入值是否比j位置的值小if (tmp arr[j]) {//小位置不对将该位置的值往后挪继续找arr[j 1] arr[j];} else {//大找到合适位置退出循环arr[j 1] tmp;break;}}//当待插入值最小时将待插入值插入到第一个位置当找到合适位置将待插入值插入合适位置arr[j 1] tmp;}} ♪算法稳定性 当相邻的元素比较大小时若相等直接插入排序不会改变它们的位置因此保证了排序前后相等元素的相对位置不变故直接插入排序是稳定的排序。 ♪时间复杂度 ♩最好情况排序一组有序序列对n-1个元素进行插入操作由于每个元素都不需要移动故时间复杂度为O(n)。♩最坏情况排序一组逆序序列对n-1个元素进行插入操作每个元素对应的移动次数依次为1、2、3、....、n-1等差数列求和得(n-1)(1n-1)/2n(n-1)/2(n^2-n)/2故算法时间复杂度为O(n^2)。 注数组越稳定使用直接插入排序时效率越高 ♪空间复杂度 只需要一个额外的空间存放待插入值故空间复杂度为O(1)。 ♫希尔排序 ♪基本思想 我们知道序列越有序直接插入排序的效率越高而希尔排序就是先通过局部的直接插入排序将序列变得相对有序后再进行整体的直接插入排序的排序算法希尔排序也叫作缩小增量排序。希尔排序法的基本思想是① 先取gap作为第一个增量把序列根据gap分组。② 所有距离为gap的倍数的记录放在同一个组中在各组内进行直接插入排序。③ 取第二个缩小的增量gap2重复上述的分组和排序直至所取的增量gap1即所有记录放在同一组中进行直接插入排序为止。 以gap为元素个数的一半每次gap的值缩小一半为例 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样整体的直接插入排序就会很快。 ♪算法实现 这里依然以gap为元素个数的一半每次gap的值缩小一半为例 //希尔排序从小到大public void shellSort(int[] arr) {//可数组不用排if (arr null) {return;}//增量的大小取数组元素的个数的一半int gap arr.length / 2;//增量每次缩小一半直至为减为1for (; gap 0; gap / 2) {//对数组进行指定增量的直接插入排序shell(arr, gap);}}//指定增量的直接插入排序public void shell(int[] arr, int gap) {//从第一组的第二个元素开始直到整个数组的最后一个元素for (int i gap; i arr.length; i) {//取出待插入的元素int tmp arr[i];int j 0;//从每组待插入元素的位置到该组的第一个元素for (j i - gap; j 0; j - gap) {//判断待插入值是否比j位置的值小if (tmp arr[j]) {//小位置不对将该位置的值往后挪继续找arr[j gap] arr[j];} else {//大找到合适位置退出循环arr[j gap] tmp;break;}}//当待插入值最小时将待插入值插入到第一个位置当找到合适位置将待插入值插入合适位置arr[j gap] tmp;}} ♪算法稳定性 因为希尔排序的是缩小增量的插入排序无法保证每次分组相同元素都在同一组故希尔排序是不稳定的排序。 ♪时间复杂度 希尔排序的时间复杂度根据gap取法的不同而不同上述取法的时间复杂度约为O(n^1.25)~O(1.6*n^1.25)之间其中n为数组中元素的个数。 ♪空间复杂度 希尔排序的空间复杂度和直接插入排序一样都是O(1)。 ♫直接选择排序 ♪基本思想 直接选择排序的基本思想是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 ♪算法实现 //选择排序从小到大public void selectSort(int[] arr) {//空数组不用排if (arr null) {return;}//从第一个元素开始到倒二个元素for (int i 0; i arr.length-1; i) {//记录i及其i后面元素的最小值int minIndex i;//找出i及其后面最小元素的下标for (int j i 1; j arr.length; j) {if (arr[minIndex] arr[j]) {minIndex j;}}//将最小元素的位置移到i位置if (i ! minIndex) {int tmp arr[i];arr[i] arr[minIndex];arr[minIndex] tmp;}}} ♪算法稳定性 在选择排序中如果数组中有两个相等的元素在选择排序的过程中可能会先选中后面的元素导致它们的原始位置交换这样就破坏了它们在原数组中的相对顺序故直接选择排序是不稳定的排序。 ♪时间复杂度 对n-1个元素进行操作每个元素对应的比较次数依次为n-1n-2n-3...1等差数列求和得(n-1)(1n-1)/2n(n-1)/2(n^2-n)/2故算法时间复杂度为O(n^2)。 ♪空间复杂度 直接选择排序只需要一个额外的常数级别的空间来交换元素因此直接选择排序的空间复杂度为O(1)。 ♫堆排序 ♪基本思想 堆排序是指利用堆这种数据结构所设计的一种排序算法它是通过堆来进行选择数据排升序要建大堆排降序建小堆是选择排序的一种。堆排序的基本思想是 ①.将待排序序列构造成一个大/小根堆。②.将其与末尾元素进行交换 此时末尾就为最大值。③.然后将剩余的个元素重新调整成一个大/小根堆反复执行上述操作 便能得到一个有序序列了。 ♪算法实现 //堆排序从小到大public void heapSort(int[] arr) {//空数组不用排if (arr null) {return;}//创建大根堆createBigHeap(arr);int end arr.length - 1;while (end 0) {//将堆顶元素和堆的最后一个元素交换int tmp arr[0];arr[0] arr[end];arr[end] tmp;//将剩余元素重新调整为大根堆shiftDown(arr, 0, end);//堆的个数减一end--;}}//创建大根堆private void createBigHeap(int[] arr) {//从最右边的叶子节点开始for (int parent (arr.length - 1 - 1) / 2; parent 0; parent--) {//向下调整shiftDown(arr, parent, arr.length);}}//向下调整private void shiftDown(int[] arr, int parent, int len) {//child为parent的左孩子右孩子可能不存在int child 2 * parent 1;while (child len) {//child为parent的左右孩子节点中的最小节点if (child 1 len arr[child] arr[child 1]) {child child 1;}//大根堆parent节点应该是parent节点和child节点中最大的那个节点if (arr[parent] arr[child]) {int tmp 0;arr[parent] tmp;arr[parent] arr[child];arr[child] tmp;//继续向下调整parent child;child 2 * parent 1;} else {//已经是大根堆了退出循环break;}}} ♪算法稳定性 因为在调整堆的过程中会进行多次元素的交换这样可能会打破原本相等元素之间的相对位置关系故堆排序是不稳定的排序。 ♪时间复杂度 初始化堆的时间复杂度为O(n)删除操作的时间复杂度为O(logn)每删除一个元素总元素减一n-1次的删除操作的时间应该为log(n)log(n-1)…log(3)log(2) log(n!) 又因(n/2)^(n/2) ≤ n ≤ n^n即 1/4*nlog(n) ≤ n! ≤ nlogn去掉常数后时间复杂度为O(nlogn)故堆排序的时间复杂度为O(nlogn)。 ♪空间复杂度 堆排序是一种原地排序算法所有操作都在原始的数组中进行故堆排序的空间复杂度为O(1)。 ♫冒泡排序 ♪基本思想 冒泡排序可以看成冒泡的过程每次排序都会让一个“泡泡”指一个元素浮到数组的正确位置。冒泡排序的基本思想是①从数组的第一个元素开始比较相邻的两个元素。②如果相邻的两个元素顺序不符合要求比如升序排序时前一个数大于后一个数则交换这两个元素的位置。③继续比较下一个相邻的两个元素直到数组的末尾。④重复以上步骤每次比较时都从数组的第一个元素开始直到数组完全有序为止。 ♪算法实现 //冒泡排序从小到大public void bubbleSort(int[] arr) {//空数组不用排if (arr null) {return;}//总共需要对对n-1个元素进行比较for (int i 0; i arr.length - 1; i) {boolean flg false;//每个元素和n-1-i个元素进行比较i为序列后面已经有序的元素for (int j 0; j arr.length - 1 - i; j) {//比较相邻两个元素大的往后移if (arr[j] arr[j 1]) {int tmp arr[j 1];arr[j 1] arr[j];arr[j] tmp;//进行过交换操作当前序列仍未有序flg true;}}//不需要进行交换操作当前序列已经有序了if (flg false) {break;}}} ♪算法稳定性 在冒泡排序中只有前后元素比较大小并进行交换而相同元素之间是不会交换的故冒泡排序是一种稳定的排序。 ♪时间复杂度 在最坏的情况下即序列本来就是逆序的情况下需要进行n-1次遍历每次遍历需要比较和交换n-i次因此总的比较和交换次数是n(n-1)/2故冒泡排序的时间复杂度是O(n^2)。 ♪空间复杂度 因为冒泡排序只需要一个常量级别的额外空间来交换相邻的元素故冒泡排序的空间复杂度为O(1)。 ♫快速排序 ♪基本思想 快速排序Quicksort是一种高效的排序算法基于分治的思想通过不断地将待排序序列划分为独立的两部分然后对每一部分递归地进行快速排序最终得到有序序列。 快速排序的基本思想是 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 ♪算法实现 //快速排序从小到大public void quickSort(int[] arr) {//空数组不用排if (arr null) {return;}//对整个数组进行快速排序quick(arr, 0, arr.length - 1);}private void quick(int[] arr, int start, int end) {//递归结束条件if (end start) {return;}//获取基准数的位置int pivot partition(arr, start, end);//对基准数的左边进行快速排序quick(arr, start, pivot - 1);//对基准数的右边进行快速排序quick(arr, pivot 1, end);} 其中找基准数的代码根据基准值划分区间的方式不同算法的实现也就不同常见的划分区间的方式有 ♩. Hoare法 Hoare法的具体步骤如下 ①.首先选择一个pivot元素将待排序数组分成左右两部分 ②.然后将左右两部分分别用一个指针来遍历数组 ③.左指针指向左部分的第一个元素右指针指向右部分的最后一个元素 ④.左指针向右移动直到找到第一个大于等于pivot的元素 ⑤.右指针向左移动直到找到第一个小于等于pivot的元素 ⑥.如果左指针和右指针还没有相遇则将它们所指的元素交换 ⑦.重复步骤4-6直到左指针和右指针相遇 ⑧.最后将pivot元素放到相遇点的位置上使得左部分的元素都小于等于pivot右部分的元素都大于等于pivot ⑨.递归地对左右两部分进行排序直到整个数组有序。 代码实现 //Hoare法找基准数private int partition(int[] arr, int left, int right) {int n left;//初始基准int pivot arr[left];while (left right) {//从右边开始找比基准数大的while (left right arr[right] pivot) {right--;}//从左边找比基准数小的while (left right arr[left] pivot) {left;}//左边小的和右边打的交换int tmp arr[left];arr[left] arr[right];arr[right] tmp;}//left和right相遇了将left和初始基准数交换int tmp arr[n];arr[n] arr[left];arr[left] tmp;//返回新基准数leftreturn left;} 注只能先从右边找比基准数大的数如果先从左边找比基准数小的数的话最后和基准数交换的时候会把比基准数大的数换到基准数前面。 ♩挖坑法 挖坑法的具体步骤如下 ①.选定一个基准元素通常选择第一个元素或最后一个元素。 ②.将序列分为两部分一部分为小于基准元素的部分一部分为大于等于基准元素的部分。 ③.在小于基准元素的部分中从右到左寻找第一个大于等于基准元素的元素将该元素赋值到基准元素的位置。 ④.在大于等于基准元素的部分中从左到右寻找第一个小于基准元素的元素将该元素赋值到第3步所挖的坑中。 ⑤.重复3、4步直到左右两部分扫描相遇然后将基准元素放回该位置。 ⑥.递归地对左右两部分进行快速排序 代码实现 //挖坑法找基准数
private int partition(int[] arr, int left, int right) {//记录初始基准数int pivot arr[left];while (left right) {//从右边开始找比基准数大的while (left right arr[right] pivot) {right--;}//将右边大的放到left位置arr[left] arr[right];//从右边开始找比基准数大的while (left right arr[left] pivot) {left;}//将左边小的放到left位置arr[right] arr[left];}//left和right相遇将初始基准数放到left位置arr[left] pivot;//返回新基准数leftreturn left;
} ♩前后指针法 前后指针法的步骤为 ①.选取一个基准数一般选择第一个数或最后一个数 ②.定义前后指针i和j分别指向数列的开头和结尾 ③.从后往前找到第一个比基准数小的数记录其坐标j ④.从前往后找到第一个比基准数大的数记录其坐标i ⑤.如果i j则交换i和j的位置使得比基准数大的数在右侧比基准数小的数在左侧 ⑥.重复③、④、⑤步骤直到i j此时前后指针相遇 ⑦.交换基准数和前后指针相遇的位置即将基准数放入正确的位置 ⑧.将数列分成两个部分分别对左边和右边的部分重复以上步骤直到整个数列有序。 代码实现 //前后指针法找基准数private int partition(int[] arr, int left, int right) {int prev left, cur left1;while (cur right) {while (arr[cur] arr[left] arr[prev] ! arr[cur]) {int tmp arr[cur];arr[cur] arr[prev];arr[prev] tmp;}cur;}int tmp arr[left];arr[left] arr[prev];arr[prev] tmp;return prev;} ♪算法的优化 ♩三数取中 当取到的基准数为最大或最小时快速排序的效率是比较低的故我们可以通过选取最左边中间最右边三个数的中间值降低取到的基准数最大或最小的情况。 private void quick(int[] arr, int start, int end) {//递归结束条件if (end start) {return;}//找到下标为start、end、(startend)/2中的数中第二大的数的小标int MidIndex findMidValOfIndex(arr, start, end);//确保三个数中第二大的在start位置if (MidIndex ! start) {int tmp arr[start];arr[start] arr[MidIndex];arr[MidIndex] tmp;}//获取下一个基准数的位置int pivot partition(arr, start, end);//对基准数的左边进行快速排序quick(arr, start, pivot - 1);//对基准数的右边进行快速排序quick(arr, pivot 1, end);}//找到下标为start、end、(startend)/2中的数中第二大的数的小标private int findMidValOfIndex(int[] array, int start, int end) {int midIndex (startend) / 2;if(array[start] array[end]) {if(array[midIndex] array[start]) {return start;}else if(array[midIndex] array[end]) {return end;}else {return midIndex;}}else {if(array[midIndex] array[start]) {return start;}else if(array[midIndex] array[end]) {return end;}else {return midIndex;}}}♩小区间快排 快速排序越排是越有序的故当待排序序列长度较小时插入排序的性能可能比快速排序更优。因此可以在递归深度达到一定阈值时使用插入排序来处理子序列。 private void quick(int[] arr, int start, int end) {//递归结束条件if (end start) {return;}//递归到小区间时用直接插入排序if (end - start 1 15) {insertSort(arr, start, end);return;}//找到下标为start、end、(startend)/2中的数中第二大的数的小标int MidIndex findMidValOfIndex(arr, start, end);//确保三个数中第二大的在start位置if (MidIndex ! start) {int tmp arr[start];arr[start] arr[MidIndex];arr[MidIndex] tmp;}//获取下一个基准数的位置int pivot partition(arr, start, end);//对基准数的左边进行快速排序quick(arr, start, pivot - 1);//对基准数的右边进行快速排序quick(arr, pivot 1, end);}//直接插入排序private void insertSort(int[] arr, int left, int right) {for (int i left1; i right; i) {int tmp arr[i];int j 0;for (j i-1; j left; j--) {if (arr[j] tmp) {arr[j1] arr[j];} else {break;}}arr[j1] tmp;}} ♪算法稳定性 在快速排序中如果两个元素的值相同它们在排序后可能会交换位置因此快速排序是不稳定的排序。 ♪时间复杂度 快速排序的时间复杂度取决于分割点选择的方法如果每次选择中位数作为分割点则最坏时间复杂度为O(n^2)平均时间复杂度为O(n log n)如果分割点随机选择则最坏时间复杂度为O(n^2)的概率很小平均时间复杂度为O(n log n)。因此快速排序的平均时间复杂度为O(n log n)最坏时间复杂度为O(n^2)。 ♪空间复杂度 快速排序的空间复杂度为 O(nlogn)其中 n 为排序的元素个数。这是因为快速排序是一种原地排序算法它只需要将排序过程中所需的一些暂存空间复用不会额外占用大量的内存空间。而在最坏情况下快速排序的空间复杂度可能会退化为 O(n)但这种情况非常罕见。 ♫归并排序 ♪基本思想 归并排序是一种分治算法是将一个大的问题分解成若干个小问题来解决然后将这些小问题的解合并起来得到原始问题的解。归并排序的基本思想是先将待排序的序列分成两个部分直到每个部分只有一个元素为止再将两个单元素部分归并成一个有序序列直到所有序列都合并成一个有序序列为止。 ♪算法实现 //归并排序从小到大public void mergeSort(int[] arr) {mergeSortChild(arr, 0, arr.length-1);}public void mergeSortChild(int[] arr, int left, int right) {if (left right) {return;}int mid (leftright) / 2;mergeSortChild(arr, left, mid);mergeSortChild(arr, mid1, right);merge(arr,left,mid,right);}private static void merge(int[] arr,int left,int mid,int right) {int s1 left;int e1 mid;int s2 mid1;int e2 right;int[] tmpArr new int[right-left1];int k 0;//表示tmpArr 的下标while (s1 e1 s2 e2) {if(arr[s1] arr[s2]) {tmpArr[k] arr[s1];}else{tmpArr[k] arr[s2];}}while (s1 e1) {tmpArr[k] arr[s1];}while (s2 e2) {tmpArr[k] arr[s2];}//tmpArr当中 的数据 是right left 之间有序的数据for (int i 0; i k; i) {arr[ileft] tmpArr[i];}} ♪算法的稳定性 归并排序在合并两个有序子序列的时候如果两个元素的大小相同那么在归并的结果中左边的元素肯定会先被放入序列中也就是说它们的相对顺序没有改变。故归并排序是一种稳定的排序。 ♪时间复杂度 归并排序在排序过程中先将待排序的序列递归地拆分为两个子序列每次拆分会将序列长度缩小一半。然后将两个子序列合并成一个有序的序列合并操作的时间复杂度为O(n)。整个排序过程中序列被拆分成了logn级别的子序列每个子序列都要进行一次合并操作所以时间复杂度为O(nlogn)。 ♪空间复杂度 在归并排序中需要创建一个额外的数组来保存排序的结果在归并过程中需要不断地合并两个有序数组因此需要创建一个长度为n的数组来保存排序后的结果。另外在归并排序的递归过程中需要创建一个长度为n的临时数组来保存每次递归的中间结果所以归并排序的空间复杂度为O(n)。 ♫排序算法的比较 排序算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定希尔排序O(n)O(n^2)O(n^1.3)O(1)不稳定堆排序O(n*logn)O(n*logn)O(n*logn)O(1)不稳定快速排序O(n*logn)O(n^2)O(n*logn)O(logn)~O(n)不稳定归并排序O(n*logn)O(n*logn)O(n*logn)O(n)稳定
