Java基础学习总结（28）——Java对各种排序算法的实现
2024-08-26 00:53:38
这里总结下各种排序算法的java实现
冒泡排序
public class BubbleSort {
publicstaticint[] bubbleSort(int[] array) {
if(array == null) {
returnnull;
}
for(inti = 0; i < array.length; i++) {
for(intj = 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];
}
}
}
returnarray;
}
}
插入排序
public class InsertSort {
publicstaticint[] insertSort(int[] array) {
if(array == null) {
returnnull;
}
for(inti = 1; i < array.length; i++) {
for(intj = i; (j > 0) && (array[j] < array[j - 1]); j--) {
SortUtils.swap(array, j, j - 1);
}
}
returnarray;
}
}
选择排序
public class SelectionSort {
publicstaticint[] selectionSort(int[] array) {
if(array == null) {
returnnull;
}
for(inti = 0; i < array.length; i++) {
intlowIndex = i;
for(intj = array.length - 1; j > i; j--) {
if(array[j] < array[lowIndex]) {
lowIndex = j;
}
}
SortUtils.swap(array, i, lowIndex);
}
returnarray;
}
}
?
Shell排序
public class ShellSort {
publicstaticint[] shellSort(int[] array) {
if(array == null) {
returnnull;
}
for(inti = array.length / 2; i > 2; i /= 2) {
for(intj = 0; j < i; j++) {
insertSort(array, j, i);
}
}
insertSort(array,0,1);
returnarray;
}
privatestaticvoidinsertSort(int[] array, intstart,intinc) {
for(inti = start + inc; i < array.length; i += inc) {
for(intj = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) {
SortUtils.swap(array, j, j - inc);
}
}
}
}
?
快速排序
public class QKSort {
publicstaticint[] quickSort(int[] array) {
if(array != null) {
returnquickSort(array,0, array.length - 1);
}
returnnull;
}
privatestaticint[] quickSort(int[] array, intbeg,intend) {
if(beg >= end || array == null) {
returnnull;
}
intp = partition(array, beg, end);
quickSort(array, beg, p - 1);
quickSort(array, p + 1, end);
returnarray;
}
/**
* 找到分界点
* @param array
* @param beg
* @param end
* @return
*/
privatestaticintpartition(int[] array, intbeg,intend) {
intlast = array[end];
inti = beg - 1;
for(intj = 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];
}
returni + 1;
}
}
堆排序
public class HeapSort {
publicstaticint[] heapSort(int[] array) {
if(array == null) {
returnnull;
}
MaxHeap h = newMaxHeap();
h.init(array);
for(inti = 0; i < array.length; i++) {
h.remove();
}
System.arraycopy(h.queue,1, array, 0, array.length);
returnarray;
}
privatestaticclassMaxHeap {
voidinit(int[] data) {
this.queue = newint[data.length + 1];
for(inti = 0; i < data.length; i++) {
queue[++size] = data[i];
fixUp(size);
}
}
privateintsize = 0;
privateint[] queue;
publicintget() {
returnqueue[1];
}
publicvoidremove() {
SortUtils.swap(queue,1, size--);
fixDown(1);
}
// fixdown
privatevoidfixDown(intk) {
intj;
while((j = k << 1) <= size) {
if(j < size && queue[j] < queue[j + 1]) {
j++;
}
// 不用交换
if(queue[k] > queue[j]) {
break;
}
SortUtils.swap(queue, j, k);
k = j;
}
}
privatevoidfixUp(intk) {
while(k > 1) {
intj = k >> 1;
if(queue[j] > queue[k]) {
break;
}
SortUtils.swap(queue, j, k);
k = j;
}
}
}
}
归并排序
public class MergeSort {
publicstaticint[] mergeSort(int[] array) {
if(array == null) {
returnnull;
}
int[] temp = newint[array.length];
returnmergeSort(array, temp, 0, array.length - 1);
}
privatestaticint[] mergeSort(int[] array, int[] temp, intl,intr) {
intmid = (l + r) / 2;
if(l == r) {
returnnull;
}
mergeSort(array, temp, l, mid);
mergeSort(array, temp, mid + 1, r);
for(inti = l; i <= r; i++) {
temp[i] = array[i];
}
inti1 = l;
inti2 = mid + 1;
for(intcur = l; cur <= r; cur++) {
if(i1 == mid + 1) {
array[cur] = temp[i2++];
}elseif(i2 > r) {
array[cur] = temp[i1++];
}elseif(temp[i1] < temp[i2]) {
array[cur] = temp[i1++];
}else{
array[cur] = temp[i2++];
}
}
returnarray;
}
}
归并排序(改进)
public class MergeSortImproved {
privatestaticfinalint THRESHOLD = 10;
publicstaticint[] mergeSort(int[] array) {
if(array == null) {
returnnull;
}
int[] temp = newint[array.length];
returnmergeSort(array, temp, 0, array.length - 1);
}
privatestaticint[] mergeSort(int[] array, int[] temp, intl,intr) {
inti, j, k;
intmid = (l + r) / 2;
if(l == r) {
returnnull;
}
if((mid - l) >= THRESHOLD) {
mergeSort(array, temp, l, mid);
}else{
insertSort(array, l, mid - l + 1);
}
if((r - mid) > THRESHOLD) {
mergeSort(array, temp, mid + 1, r);
}else{
insertSort(array, mid + 1, 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];
}
inta = temp[l];
intb = 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];
}
}
returnarray;
}
privatestaticvoidinsertSort(int[] array, intstart,intlen) {
for(inti = start + 1; i < start + len; i++) {
for(intj = i; (j > start) && array[j] < array[j - 1]; j--) {
SortUtils.swap(array, j, j - 1);
}
}
}
}
最新文章
- webbench---linux压测工具
- hdu 4165 Pills dp
- jq layer插件使用
- js 后台异步执行
- hdu 2553 N皇后问题 (经典DFS)
- Java学习----Java程序结构
- Android 按钮按下效果
- VS2010调试小技巧
- SQL Server数据库连接字符串整理
- 转: js中的getYear()函数的问题(推荐用 getFullYear())
- ASP.NET - 对URL传递的值进行编码Server.UrlEncode()
- POJ 1284 Primitive Roots 原根
- JAVA实用案例之水印开发
- javascript常用的Math对象的方法
- tensorflow第一篇---numpy模块
- ssh框架搭建出现的异常： class com.my.entity.user not found while looking for property: id
- PCB设计检查
- gets函数
- 17秋 SDN课程 第一次作业
- python截取字符串