最新java中常用的七大排序算法.doc

《最新java中常用的七大排序算法.doc》由会员分享，可在线阅读，更多相关《最新java中常用的七大排序算法.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品资料java中常用的七大排序算法.java中常用的七大排序算法java中常用的七大排序算法这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！1.插入排序算法插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 0.i-1 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2) 和 O(1)。/* param int 未排序数组* return i

2、nt 排完序数组*/public int sortInsert(int array)for(int i=1;i= 0 & temp arrayj; j-)arrayj + 1 = arrayj;arrayj + 1 = temp;return array;2.选择排序算法选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 in-1 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2)和O(1)。/* param i

3、nt 未排序数组* return int 排完序数组*/public int sortSelect(int arr)for (int i = 0; i arr.length; i+) int miniPost = i;for (int m = i + 1; m arr.length; m+) if (arrm arrminiPost) int temp;temp = arri;arri = arrminiPost;arrminiPost = temp;return arr;3.冒泡排序算法冒泡排序的基本思想是將比較大的數字沉在最下面，较小的浮在上面。冒泡排序的时间复杂度和空间复杂度分别是O(n

4、2)和O(1)。/* param int 未排序数组* return int 排完序数组*/public int sortBubble(int array)int temp;/ 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）for(int i=0;i i; j-) if (arrayj arrayj - 1) temp = arrayj;arrayj = arrayj - 1;arrayj - 1 = temp;return array;4.快速排序算法通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的

5、关键字小，则可以分别对这两部分记录继续进行排序，已达到整个序列有序的目的，本质就是，找一个基位(枢轴，分水岭，作用是左边的都比它小，右边的都比它大。)基位可随机选取，取名base，首先从序列最右边开始找比base小的，如果小，换位置，从而base移到刚才右边(比较时比base小)的位置(记为临时的high位)，这样base右边的都比base大。然后从序列的最左边开始找比base大的，如果大，换位置，从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位)，这样base左边的都比base小，循环以上两步，直到 low = heigh，这使才真正的找到了枢轴-分水岭。返回这个位

6、置，分水岭左边和右边的序列，分别再来递归。快速排序的时间复杂度和空间复杂度都是O(nlogn)。/* param int 未排序数组* return int 排完序数组*/public int sortQuick(int array)return quickSort(array, 0, array.length-1);private int quickSort(int arr, int low, int heigh) if (low heigh) int division = partition(arr, low, heigh);quickSort(arr, low, division - 1

7、);quickSort(arr, division + 1, heigh);return arr;/ 分水岭,基位,左边的都比这个位置小,右边的都大private int partition(int arr, int low, int heigh) int base = arrlow; /用子表的第一个记录做枢轴(分水岭)记录while (low heigh) /从表的两端交替向中间扫描while (low = base) heigh-;/ base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大swap(arr, heigh, low);whi

8、le (low heigh & arrlow = base) low+;/ 遇到左边比base值大的了,换位置swap(arr, heigh, low);/ now low = heigh;return low;private void swap(int arr, int a, int b) int temp;temp = arra;arra = arrb;arrb = temp;5.合并排序算法归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过

9、程中需要额外的跟需要归并的两个数组长度一致的空间合并排序的时间复杂度和空间复杂度是O(nlogn)和O(n)。/* param int 未排序数组* return int 排完序数组*/private int sort(int nums, int low, int high) int mid = (low + high) / 2;if (low high) / 左边sort(nums, low, mid);/ 右边sort(nums, mid + 1, high);/ 左右归并merge(nums, low, mid, high);return nums;private void merge(

10、int nums, int low, int mid, int high) int temp = new inthigh - low + 1;int i = low;/ 左指针int j = mid + 1;/ 右指针int k = 0;/ 把较小的数先移到新数组中while (i = mid & j = high) if (numsi numsj) tempk+ = numsi+; else tempk+ = numsj+;/ 把左边剩余的数移入数组while (i = mid) tempk+ = numsi+;/ 把右边边剩余的数移入数组while (j = high) tempk+ =

11、numsj+;/ 把新数组中的数覆盖nums数组for (int k2 = 0; k2 = 1) for (int i = step; i = 0 & temp = 1; i-) swap(array, 0, i);heapify(array, 0, i);return array;private void buildHeap(int array) int n = array.length;/ 数组中元素的个数for (int i = n / 2 - 1; i = 0; i-)heapify(array, i, n);private void heapify(int A, int idx, i

12、nt max) int left = 2 * idx + 1;/ 左孩子的下标（如果存在的话）int right = 2 * idx + 2;/ 左孩子的下标（如果存在的话）int largest = 0;/ 寻找3个节点中最大值节点的下标if (left Aidx)largest = left;elselargest = idx;if (right Alargest)largest = right;if (largest != idx) swap(A, largest, idx);heapify(A, largest, max);/ 建堆函数，认为【s，m】中只有 s/ 对应的关键字未满足大

13、顶堆定义，通过调整使【s，m】成为大顶堆=public static void heapAdjust(int array, int s, int m) / 用0下标元素作为暂存单元array0 = arrays;/ 沿孩子较大的结点向下筛选for (int j = 2 * s; j = m; j *= 2) / 保证j为较大孩子结点的下标，j m 保证 j+1 = m ，不越界if (j m & arrayj arrayj + 1) j+;if (!(array0 arrayj) break;/ 若S位较小，应将较大孩子上移arrays = arrayj;/ 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选s = j;/ 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。arrays = array0;