Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)
本文实例汇总了Java各种排序算法。分享给大家供大家参考，具体如下：
1. 冒泡排序：
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
show(a);
bubbleSort(a);
show(a);
}
private static void bubbleSort(int[] a) {
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
2. 快速排序(无重复值)：
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,3,12,23,110};
show(a);
quickSort(a,0,a.length-1);
show(a);
}
private static void quickSort(int[] a, int start, int end) {
if (start>=end)
return;
int i=start;
int j=end;
int index = start;
while(i<j){
while(a[j]>a[index]){
j--;
}
index = swap(a,j,index);
while(a[index]>a[i]){
i++;
}
index = swap(a,i,index);
}
quickSort(a, start, index-1);
quickSort(a, index+1, end);
}
private static int swap(int[] a, int n, int index) {
int tmp = a[n];
a[n] = a[index];
a[index] = tmp;
return n;
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
3. 快速排序（可含重复值）
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,345};
show(a);
quickSort2(a,0,a.length-1);
show(a);
}
private static void quickSort2(int[] a, int start, int end) {
if (start>=end)
return;
int i=start;
int j=end;
int index = end;
while(i<j){
while(a[j]>a[index]){
j--;
}
if (j!=index && a[j]==a[index]){
index = swap(a,--j,index);
}else{
index = swap(a,j,index);
}
while(a[index]>a[i]){
i++;
}
if (i!=index && a[i]==a[index]){
index = swap(a,++i,index);
}else{
index = swap(a,i,index);
}
}
quickSort2(a, start, index-1);
quickSort2(a, index+1, end);
}
private static int swap(int[] a, int n, int index) {
int tmp = a[n];
a[n] = a[index];
a[index] = tmp;
return n;
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
4. 堆排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
show(a);
heapSort(a);
show(a);
}
private static void heapSort(int[] a) {
//建立最大堆
int size = a.length;
for(int i=size/2-1;i>=0;i--){
createBigHeap(a,i,size-1);
}
//排序
for(int j=0;j<size-1;j++){
int tmp=a[0];
a[0]=a[size-1-j];
a[size-1-j]=tmp;
createBigHeap(a,0,size-2-j);
}
}
private static void createBigHeap(int[] a, int start, int end) {
int tmp = a[start];
int j = 2*start+1;
while(j<=end){
if (j<end && a[j]<a[j+1]){
j++;
}
if (a[j]>tmp){
a[start] = a[j];
start = j;
j = 2*j+1;
}else{
break;
}
}
a[start] = tmp;
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
5. 插入排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3};
show(a);
insertSort(a);
show(a);
}
private static void insertSort(int[] a) {
for(int i=0;i<a.length-1;i++){
int n = i+1;
int tmp = a[n];
for(int j=i;j>=0;j--){
if(tmp<a[j]){
a[n] = a[j];
n=j;
}
}
if (a[n]!=tmp)
a[n] = tmp;
}
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
6. 折半插入排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,7,345,2,2,7,2,7,23,2,345,7,32,5,4,-1,3,7,2,3,2,3,4,2,1,2,4,5,3,345,3,2};
show(a);
insertSort2(a);
show(a);
}
private static void insertSort2(int[] a) {
for(int i=0;i<a.length-1;i++){
int n = i+1;
int tmp = a[n];
if (tmp>a[i])
continue;
int low = 0;
int high = i;
int mid = (high+low)/2;
while(high>=low){
mid = (high+low)/2;
if(tmp<a[mid]){
high = mid -1;
}else if(tmp>a[mid]){
low = mid + 1;
} else{
low=mid;
break;
}
}
for(int j=n;j>mid;j--){
a[j] = a[j-1];
}
a[low] = tmp;
}
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
7. 希尔排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1};
show(a);
shellSort(a);
show(a);
}
private static void shellSort(int[] a) {
shellSort(a,a.length);
}
private static void shellSort (int[] a, int n){
int i, j, k, temp, gap;
int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647 };
for (k=0; gaps[k]<n; k++);
while (--k >= 0){
gap = gaps[k];
for (i=gap; i<n; i++){
temp = a[i];
j = i;
while (j>=gap && a[j-gap]>temp){
a[j] = a[j-gap];
j = j-gap;
}
a[j] = temp;
}
}
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
8. 选择排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1};
show(a);
selectSort(a);
show(a);
}
private static void selectSort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
int min = i;
for (int j = i+1; j < a.length; j++) {
if (a[j]<a[min])
min = j;
}
if (min!=i){
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
9. 归并排序
public class SortTest {
public static void main(String[] args) {
int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1,432,1};
show(a);
mergeSort(a);
show(a);
}
private static void mergeSort(int[] a) {
//找出中间值
int mid = a.length/2;
//申请空间存储中间索引以左的值
int[] left = setValue(a,0,mid);
if (left.length>1){//继续拆分左边，直到元素值为1个
mergeSort(left);
}
//申请空间存储中间索引以右的值
int[] right = setValue(a,mid,a.length);
if (right.length>1){//继续拆分右边，直到元素值为1个
mergeSort(right);
}
//将左右值合并
merge(a,left,right);
}
private static void merge(int[] a , int[] left, int[] right) {
int i=0,j=0,k=0;
for(;i<left.length && j<right.length;){
if (left[i]<right[j]){
a[k++] = left[i++];
}else{
a[k++] = right[j++];
}
}
for(;i<left.length;i++){
a[k++] = left[i];
}
for(;j<right.length;j++){
a[k++] = right[j];
}
}
private static int[] setValue(int[] a, int start,int length) {
int[] x = new int[length-start];
for (int i = 0; i < x.length; i++) {
x[i] = a[start++];
}
return x;
}
private static void show(int[] a) {
System.out.println(Arrays.toString(a));
}
}
汇总：
public class SortUtil {
public final static int DESC = -1;
public final static int ASC = 1;
/**
* 冒泡排序
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void bubbleSort(int[] a,int sort) {
if (sort==ASC)
bubbleSortAsc(a);
else
bubbleSortDesc(a);
}
public static void bubbleSortAsc(int[] a) {
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
public static void bubbleSortDesc(int[] a) {
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]<a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
// ----------------华-丽-的-功-能-分割-线-----------------------
/**
* 快速排序（不允许有重复值）
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void quickNoRepeatSort(int[] a,int sort) {
if (sort==ASC)
quickNoRepeatSortAsc(a, 0, a.length-1);
else
quickNoRepeatSortDesc(a, 0, a.length-1);
}
private static void quickNoRepeatSortAsc(int[] a, int start, int end) {
if (start >= end)
return;
int i = start;
int j = end;
int index = start;
while (i < j) {
while (a[j] > a[index]) {
j--;
}
index = swap(a, j, index);
while (a[index] > a[i]) {
i++;
}
index = swap(a, i, index);
}
quickNoRepeatSortAsc(a, start, index - 1);
quickNoRepeatSortAsc(a, index + 1, end);
}
private static void quickNoRepeatSortDesc(int[] a, int start, int end) {
if (start >= end)
return;
int i = start;
int j = end;
int index = start;
while (i < j) {
while (a[j] < a[index]) {
j--;
}
index = swap(a, j, index);
while (a[index] < a[i]) {
i++;
}
index = swap(a, i, index);
}
quickNoRepeatSortDesc(a, start, index - 1);
quickNoRepeatSortDesc(a, index + 1, end);
}
/**
* 快速排序（允许有重复值）
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void quickSort(int[] a,int sort) {
if (sort==ASC)
quickSortAsc(a, 0, a.length-1);
else
quickSortDesc(a, 0, a.length-1);
}
private static void quickSortAsc(int[] a, int start, int end) {
if (start >= end)
return;
int i = start;
int j = end;
int index = end;
while (i < j) {
while (a[j] > a[index]) {
j--;
}
if (j != index && a[j] == a[index]) {
index = swap(a, --j, index);
} else {
index = swap(a, j, index);
}
while (a[index] > a[i]) {
i++;
}
if (i != index && a[i] == a[index]) {
index = swap(a, ++i, index);
} else {
index = swap(a, i, index);
}
}
quickSortAsc(a, start, index - 1);
quickSortAsc(a, index + 1, end);
}
private static void quickSortDesc(int[] a, int start, int end) {
if (start >= end)
return;
int i = start;
int j = end;
int index = end;
while (i < j) {
while (a[j] < a[index]) {
j--;
}
if (j != index && a[j] == a[index]) {
index = swap(a, --j, index);
} else {
index = swap(a, j, index);
}
while (a[index] < a[i]) {
i++;
}
if (i != index && a[i] == a[index]) {
index = swap(a, ++i, index);
} else {
index = swap(a, i, index);
}
}
quickSortDesc(a, start, index - 1);
quickSortDesc(a, index + 1, end);
}
private static int swap(int[] a, int n, int index) {
int tmp = a[n];
a[n] = a[index];
a[index] = tmp;
return n;
}
// ----------------华-丽-的-功-能-分割-线------------------
/**
* 堆排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void heapSort(int[] a,int sort){
if (sort==ASC)
heapSortAsc(a);
else
heapSortDesc(a);
}
public static void heapSortAsc(int[] a) {
// 建立最大堆
int size = a.length;
for (int i = size / 2 - 1; i >= 0; i--) {
createBigHeap(a, i, size - 1);
}
// 排序
for (int j = 0; j < size - 1; j++) {
int tmp = a[0];
a[0] = a[size - 1 - j];
a[size - 1 - j] = tmp;
createBigHeap(a, 0, size - 2 - j);
}
}
private static void createBigHeap(int[] a, int start, int end) {
int tmp = a[start];
int j = 2 * start + 1;
while (j <= end) {
if (j < end && a[j] < a[j + 1]) {
j++;
}
if (a[j] > tmp) {
a[start] = a[j];
start = j;
j = 2 * j + 1;
} else {
break;
}
}
a[start] = tmp;
}
public static void heapSortDesc(int[] a) {
// 建立最小堆
int size = a.length;
for (int i = size / 2 - 1; i >= 0; i--) {
createSmallHeap(a, i, size - 1);
}
// 排序
for (int j = 0; j < size - 1; j++) {
int tmp = a[0];
a[0] = a[size - 1 - j];
a[size - 1 - j] = tmp;
createSmallHeap(a, 0, size - 2 - j);
}
}
private static void createSmallHeap(int[] a, int start, int end) {
int tmp = a[start];
int j = 2 * start + 1;
while (j <= end) {
if (j < end && a[j] > a[j + 1]) {
j++;
}
if (a[j] < tmp) {
a[start] = a[j];
start = j;
j = 2 * j + 1;
} else {
break;
}
}
a[start] = tmp;
}
// ----------------华-丽-的-功-能-分割-线---------------------
/**
* 插入排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void insertSort(int[] a,int sort){
if (sort==ASC){
insertSortAsc(a);
}else{
insertSortDesc(a);
}
}
public static void insertSortAsc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int n = i + 1;
int tmp = a[n];
for (int j = i; j >= 0; j--) {
if (tmp < a[j]) {
a[n] = a[j];
n = j;
}
}
if (a[n] != tmp)
a[n] = tmp;
}
}
public static void insertSortDesc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int n = i + 1;
int tmp = a[n];
for (int j = i; j >= 0; j--) {
if (tmp > a[j]) {
a[n] = a[j];
n = j;
}
}
if (a[n] != tmp)
a[n] = tmp;
}
}
// ----------------华-丽-的-功-能-分割-线--------------------
/**
* 折半插入排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void halfInsertSort(int[] a,int sort){
if (sort==ASC){
halfInsertSortAsc(a);
}else{
halfInsertSortDesc(a);
}
}
public static void halfInsertSortAsc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int n = i + 1;
int tmp = a[n];
if (tmp > a[i])
continue;
int low = 0;
int high = i;
int mid = (high + low) / 2;
while (high >= low) {
mid = (high + low) / 2;
if (tmp < a[mid]) {
high = mid - 1;
} else if (tmp > a[mid]) {
low = mid + 1;
} else {
low = mid;
break;
}
}
for (int j = n; j > mid; j--) {
a[j] = a[j - 1];
}
a[low] = tmp;
}
}
public static void halfInsertSortDesc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int n = i + 1;
int tmp = a[n];
if (tmp < a[i])
continue;
int low = 0;
int high = i;
int mid = (high + low) / 2;
while (high >= low) {
mid = (high + low) / 2;
if (tmp > a[mid]) {
high = mid - 1;
} else if (tmp < a[mid]) {
low = mid + 1;
} else {
low = mid;
break;
}
}
for (int j = n; j > mid; j--) {
a[j] = a[j - 1];
}
a[low] = tmp;
}
}
// ----------------华-丽-的-功-能-分割-线----------------------
/**
* 希尔排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void shellSort(int[] a,int sort){
if (sort==ASC){
shellSortAsc(a,a.length);
}else{
shellSortDesc(a,a.length);
}
}
public static void shellSortAsc(int[] a, int n) {
int i, j, k, temp, gap;
int[] gaps = { 1, 5, 13, 43, 113, 297, 815, 1989, 4711, 11969, 27901,
84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
58548857, 157840433, 410151271, 1131376761, 2147483647 };
for (k = 0; gaps[k] < n; k++)
;
while (--k >= 0) {
gap = gaps[k];
for (i = gap; i < n; i++) {
temp = a[i];
j = i;
while (j >= gap && a[j - gap] > temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}
public static void shellSortDesc(int[] a, int n) {
int i, j, k, temp, gap;
int[] gaps = { 1, 5, 13, 43, 113, 297, 815, 1989, 4711, 11969, 27901,
84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
58548857, 157840433, 410151271, 1131376761, 2147483647 };
for (k = 0; gaps[k] < n; k++)
;
while (--k >= 0) {
gap = gaps[k];
for (i = gap; i < n; i++) {
temp = a[i];
j = i;
while (j >= gap && a[j - gap] < temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}
// ----------------华-丽-的-功-能-分割-线---------------------
/**
* 选择排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void selectSort(int[] a,int sort){
if (sort==ASC){
selectSortAsc(a);
}else{
selectSortDesc(a);
}
}
public static void selectSortAsc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min])
min = j;
}
if (min != i) {
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}
public static void selectSortDesc(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int max = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] > a[max])
max = j;
}
if (max != i) {
int tmp = a[i];
a[i] = a[max];
a[max] = tmp;
}
}
}
// ----------------华-丽-的-功-能-分割-线---------------------
/**
* 归并排序
*
* @param a sort Array
* @param sort SortUtil.ASC,SortUtil.DESC
*/
public static void mergeSort(int[] a,int sort){
// 找出中间值
int mid = a.length / 2;
// 申请空间存储中间索引以左的值
int[] left = setValue(a, 0, mid);
if (left.length > 1) {// 继续拆分左边，直到元素值为1个
mergeSort(left,sort);
}
// 申请空间存储中间索引以右的值
int[] right = setValue(a, mid, a.length);
if (right.length > 1) {// 继续拆分右边，直到元素值为1个
mergeSort(right,sort);
}
if (sort==ASC){
mergeAsc(a, left, right);
}else{
mergeDesc(a, left, right);
}
}
private static void mergeAsc(int[] a, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
for (; i < left.length && j < right.length;) {
if (left[i] < right[j]) {
a[k++] = left[i++];
} else {
a[k++] = right[j++];
}
}
for (; i < left.length; i++) {
a[k++] = left[i];
}
for (; j < right.length; j++) {
a[k++] = right[j];
}
}
private static void mergeDesc(int[] a, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
for (; i < left.length && j < right.length;) {
if (left[i] > right[j]) {
a[k++] = left[i++];
} else {
a[k++] = right[j++];
}
}
for (; i < left.length; i++) {
a[k++] = left[i];
}
for (; j < right.length; j++) {
a[k++] = right[j];
}
}
private static int[] setValue(int[] a, int start, int length) {
int[] x = new int[length - start];
for (int i = 0; i < x.length; i++) {
x[i] = a[start++];
}
return x;
}
}
希望本文所述对大家Java程序设计有所帮助。
赞 (0)
相关推荐
-
Java 归并排序算法、堆排序算法实例详解
基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
-
堆排序算法的讲解及Java版实现
堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆
-
Java堆排序算法详解
堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+
-
Java实现堆排序(Heapsort)实例代码
复制代码 代码如下: import java.util.Arrays; public class HeapSort { public static void heapSort(DataWraper[] data){ System.out.println("开始排序"); int arrayLength=data.length; //循环建堆 for(int i=0;i<arrayLength-1;i++){
-
详解堆排序算法原理及Java版的代码实现
概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,
-
java 数据结构之堆排序（HeapSort）详解及实例
1 堆排序 堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整.最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点. 所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的
-
深入解析堆排序的算法思想及Java代码的实现演示
一.基础知识 我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树.二叉堆又分为最大堆和最小堆. 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素.数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高. 最大堆的特性如下: 父结点的键值总是大于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最大堆 最小堆的特性如下: 父结点的键值总是小于或者等于任何一个
-
Java排序算法总结之堆排序
本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏
-
java堆排序原理及算法实现
从堆排序的简介到堆排序的算法实现等如下: 1. 简介 堆排序是建立在堆这种数据结构基础上的选择排序,是原址排序,时间复杂度O(nlogn),堆排序并不是一种稳定的排序方式.堆排序中通常使用的堆为最大堆. 2. 堆的定义 堆是一种数据结构,是一颗特殊的完全二叉树,通常分为最大堆和最小堆.最大堆的定义为根结点最大,且根结点左右子树都是最大堆:同样,最小堆的定义为根结点最小,且根结点左右子树均为最小堆. 最大堆满足其每一个父结点均大于其左右子结点,最小堆则满足其每一个父结点均小于其左右子结点. 3.
-
JAVA算法起步之堆排序实例
学习堆排序,首先需要明白堆的概念,堆是一个数组.可以近似当做完全二叉树的数组存储方式.但是跟他还有其他的性质,就是类似于二叉排序树.有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值.堆排序一般用的是最大堆,而最小堆可以构造优先队列.堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节点的值不符合最大堆的性质,那么这个值得位置