使用JAVA编写的排序算法

使用java练习的排序算法,逐渐补齐。


排序

import java.util.Arrays;
  • 选择排序
public class classSort {

public static void selectSort(int[] arr) {

for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
// 用i的下一个元素和它比较
if (arr[i]>arr[j]) {
// 交换值
arr[i]=arr[j]+arr[i]-(arr[j]=arr[i]);
}
}
}
}
  • 冒泡排序
public static void bubbleSort(int[] arr) {

for (int i = 0; i < arr.length-1 ; i++) {
// 防止越界
for (int j = 0; j < arr.length-i-1; j++) {
if (arr[j] > arr[j+1]) {
/*arr[j] = arr[j] ^ arr[j+1];
arr[j+1] =arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];*/
arr[j]=arr[j]+arr[j+1]-(arr[j+1]=arr[j]);
}
}
}
}
  • 合并排序
// 合并排序(递归)
public void mergeSort(int[] arr,int left,int right){

if (left<right) {
int mid = (left+right)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr,left,mid,right); // 合并后给arr
}
}

// merge的写法
public void merge(int[] arr,int left,int mid,int right) {
//int[] temp = new int[arr.length]; // 暂时存放
int length = right-left+1;
int temp[]=new int[length];
int i = left,
j = mid+1,
k = 0;
while ((i <= mid)&&(j <= right)) {
if (arr[i]<arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i<=mid) {
temp[k++]=arr[i++];
}
while (j<=right) {
temp[k++]=arr[j++];
}
int n=0;
for(int t=left;t<=right;t++,n++){
arr[t]=temp[n];
}
//System.out.println(Arrays.toString(temp));
//arr = Arrays.copyOf(temp, temp.length);
System.out.println(Arrays.toString(arr));
}
  • 快速排序
	// 快速排序,分开写
public static void quickSort(int[] arr,int left,int right){// 分治策略
if (left<right) {
int i = AdjustArray(arr,left,right);
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
}

public static int AdjustArray(int[] arr,int left, int right) {
int i = left,j=right;
int x = arr[left];
while (i<j) {
while (i<j&&arr[j]>=x)
j--;

if (i<j)
arr[i++]=arr[j];

while (i<j&&arr[i]<x)
i++;

if (i<j)
arr[j--]=arr[i];
}
arr[i]=x;
return i;// 返回基准数位置
}

// 快速排序,合并写
public void quickSort2(int[] arr,int left,int right) {
if (left<right) {
// 可使用中间数做基准
int i = left,j=right,x=arr[left];
while (i<j){
while (i<j&&arr[j]>=x)
j--;

if(i<j)
arr[i++] =arr[j];

while (i<j&&arr[i]<x)
i++;

if(i<j)
arr[j--] = arr[i];
}
arr[i]=x;
quickSort2(arr, left, i-1);
quickSort2(arr, i+1, right);
}
}

public static void main(String[] args) {

int[] arrTest = {2,5,1,9,3,7,4,6,8};
classSort m = new classSort();
m.quickSort2(arrTest,0,arrTest.length-1);
System.out.println(Arrays.toString(arrTest));
}

}
Author: Ykk
Link: https://ykksmile.top/posts/32334/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.