Java对各种排序算法的实现
发布时间：2020-12-14 23:18:41 所属栏目：Java 来源：网络整理
导读：今天PHP站长网 52php.cn把收集自互联网的代码分享给大家，仅供参考。 冒泡排序 public class BubbleSort { public static int[] bubbleSort(int[] array) { if (array == null) { return null; } for (int i = 0; i array
|
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家，仅供参考 冒泡排序 public class BubbleSort {
public static int[] bubbleSort(int[] array) {
if (array == null) {
return null;
}
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
}
}
return array;
}
}
插入排序 public class InsertSort {
public static int[] insertSort(int[] array) {
if (array == null) {
return null;
}
for (int i = 1; i < array.length; i++) {
for (int j = i; (j > 0) && (array[j] < array[j - 1]); j--) {
SortUtils.swap(array,j,j - 1);
}
}
return array;
}
}
选择排序 public class SelectionSort {
public static int[] selectionSort(int[] array) {
if (array == null) {
return null;
}
for (int i = 0; i < array.length; i++) {
int lowIndex = i;
for (int j = array.length - 1; j > i; j--) {
if (array[j] < array[lowIndex]) {
lowIndex = j;
}
}
SortUtils.swap(array,i,lowIndex);
}
return array;
}
}
Shell排序 public class ShellSort {
public static int[] shellSort(int[] array) {
if (array == null) {
return null;
}
for (int i = array.length / 2; i > 2; i /= 2) {
for (int j = 0; j < i; j++) {
insertSort(array,i);
}
}
insertSort(array,1);
return array;
}
private static void insertSort(int[] array,int start,int inc) {
for (int i = start + inc; i < array.length; i += inc) {
for (int j = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) {
SortUtils.swap(array,j - inc);
}
}
}
}
快速排序 public class QKSort {
public static int[] quickSort(int[] array) {
if (array != null) {
return quickSort(array,array.length - 1);
}
return null;
}
private static int[] quickSort(int[] array,int beg,int end) {
if (beg >= end || array == null) {
return null;
}
int p = partition(array,beg,end);
quickSort(array,p - 1);
quickSort(array,p + 1,end);
return array;
}
/**
* 找到分界点
* @param array
* @param beg
* @param end
* @return
*/
private static int partition(int[] array,int end) {
int last = array[end];
int i = beg - 1;
for (int j = beg; j <= end - 1; j++) {
if (array[j] <= last) {
i++;
if (i != j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
}
}
if ((i + 1) != end) {
array[i + 1] = array[i + 1] ^ array[end];
array[end] = array[i + 1] ^ array[end];
array[i + 1] = array[i + 1] ^ array[end];
}
return i + 1;
}
}
堆排序 public class HeapSort {
public static int[] heapSort(int[] array) {
if (array == null) {
return null;
}
MaxHeap h = new MaxHeap();
h.init(array);
for (int i = 0; i < array.length; i++) {
h.remove();
}
System.arraycopy(h.queue,1,array,array.length);
return array;
}
private static class MaxHeap {
void init(int[] data) {
this.queue = new int[data.length + 1];
for (int i = 0; i < data.length; i++) {
queue[++size] = data[i];
fixUp(size);
}
}
private int size = 0;
private int[] queue;
public int get() {
return queue[1];
}
public void remove() {
SortUtils.swap(queue,size--);
fixDown(1);
}
// fixdown
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && queue[j] < queue[j + 1]) {
j++;
}
// 不用交换
if (queue[k] > queue[j]) {
break;
}
SortUtils.swap(queue,k);
k = j;
}
}
private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j] > queue[k]) {
break;
}
SortUtils.swap(queue,k);
k = j;
}
}
}
}
归并排序 public class MergeSort {
public static int[] mergeSort(int[] array) {
if (array == null) {
return null;
}
int[] temp = new int[array.length];
return mergeSort(array,temp,array.length - 1);
}
private static int[] mergeSort(int[] array,int[] temp,int l,int r) {
int mid = (l + r) / 2;
if (l == r) {
return null;
}
mergeSort(array,l,mid);
mergeSort(array,mid + 1,r);
for (int i = l; i <= r; i++) {
temp[i] = array[i];
}
int i1 = l;
int i2 = mid + 1;
for (int cur = l; cur <= r; cur++) {
if (i1 == mid + 1) {
array[cur] = temp[i2++];
} else if (i2 > r) {
array[cur] = temp[i1++];
} else if (temp[i1] < temp[i2]) {
array[cur] = temp[i1++];
} else {
array[cur] = temp[i2++];
}
}
return array;
}
}
归并排序(改进) public class MergeSortImproved {
private static final int THRESHOLD = 10;
public static int[] mergeSort(int[] array) {
if (array == null) {
return null;
}
int[] temp = new int[array.length];
return mergeSort(array,int r) {
int i,k;
int mid = (l + r) / 2;
if (l == r) {
return null;
}
if ((mid - l) >= THRESHOLD) {
mergeSort(array,mid);
} else {
insertSort(array,mid - l + 1);
}
if ((r - mid) > THRESHOLD) {
mergeSort(array,r);
} else {
insertSort(array,r - mid);
}
for (i = l; i <= mid; i++) {
temp[i] = array[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = array[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l,j = r,k = l; k <= r; k++) {
if (a < b) {
array[k] = temp[i++];
a = temp[i];
} else {
array[k] = temp[j--];
b = temp[j];
}
}
return array;
}
private static void insertSort(int[] array,int len) {
for (int i = start + 1; i < start + len; i++) {
for (int j = i; (j > start) && array[j] < array[j - 1]; j--) {
SortUtils.swap(array,j - 1);
}
}
}
}
以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |