java中常用的七大排序算法

《java中常用的七大排序算法》由会员分享，可在线阅读，更多相关《java中常用的七大排序算法（8页珍藏版）》请在装配图网上搜索。

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

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

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

4、/* * paramint 未排序数组 * return int 排完序数组 */ publicint sortBubble(int array) int temp; / 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次 for(inti=0;ii; 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)。 /* * paramint 未排序数组 * return int 排完序数组 */ publicint sortQuick(int array) returnquickSort(array, 0, array.length-1); privateint quickSort(int arr, int low, intheigh) if (low heigh) int division = partition(arr, low, heigh); quickSort(arr, low, division - 1);

7、quickSort(arr, division + 1, heigh); returnarr; / 分水岭,基位,左边的都比这个位置小,右边的都大 privateint partition(int arr, int low, intheigh) 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)。 /* * paramint 未排序数组 * return int 排完序数组 */ privateint 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); returnnums;

10、 private void merge(int nums, int low, int mid, int high) int temp = new inthigh - low + 1; inti = 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+; / 把右边边剩余的数移入数组

11、while (j = high) tempk+ = numsj+; / 把新数组中的数覆盖nums数组 for (int k2 = 0; k2 = 1) for (inti = 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 (inti = n / 2 - 1; i= 0; i-) heapify(array, i, n); private

12、void heapify(int A, intidx, int max) int left = 2 * idx + 1;/ 左孩子的下标 int right = 2 * idx + 2;/ 左孩子的下标 int largest = 0;/ 寻找3个节点中最大值节点的下标 if (left Aidx) largest = left; else largest = idx; if (right Alargest) largest = right; if (largest != idx) swap(A, largest, idx); heapify(A, largest, max); / 建堆函数，

13、认为中只有 s / 对应的关键字未满足大顶堆定义，通过调整使【s，= public static void heapAdjust(int array, int s, int m) / 用0下标元素作为暂存单元 array0 = arrays; / 沿孩子较大的结点向下筛选 m】成为大顶堆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;