Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

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

for(int j=0;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

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

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

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

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

int n = i+1;

int tmp = a[n];

for(int j=i;j>=0;j--){

if(tmp

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

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

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]

while (--k >= 0){

gap = gaps[k];

for (i=gap; 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]

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

if (left[i]

a[k++] = left[i++];

}else{

a[k++] = right[j++];

}

}

for(;i

a[k++] = left[i];

}

for(;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

for(int j=0;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

for(int j=0;j

if(a[j]

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

* @JYMCPparam 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程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。