Various sorting algorithms implemented in Java (including bubbling, fast sorting, etc.)
// Heap sorting is unstable. Import Java util. Arrays;
public class HeapSort { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; int arrayLength=a.length; // Cyclic heap building for (int i = 0; I < arraylength-1; I + +) {/ / heap building buildmaxheap (a, arraylength-1-i); / / swap the heap top and the last element swap (a, arraylength-1-i); system.out.println (arrays. ToString (a));}}// Create a large top heap for the data array from 0 to lastindex public static void buildmaxheap (int [] data, int lastindex) {/ / start from the parent node of the node (the last node) at lastindex for (int i = (lastindex-1) / 2; I > = 0; I --) {/ / K save the node being judged int k = I; / / if the child node of the current K node exists while (K2 + 1 < = lastindex) {/ / the index of the left child node of node K, int biggerindex = 2K + 1; / / if biggerindex is less than lastindex, that is, the right child node of node K represented by biggerindex + 1 has if (biggerindex < lastindex) {/ / if the value of the right child node is large, if (data [biggerindex] < data [biggerindex + 1]) {/ / biggerindex always records the index of the larger child node, biggerindex + +;}}// If the value of node K is less than the value of its larger child nodes if (data [k] < data [biggerindex]) {/ / swap them (data, K, biggerindex); / / assign biggerindex to K, start the next cycle of the while cycle, and re ensure that the value of node K is greater than the value of its left and right child nodes k = biggerindex;} else{ break; } } } } // Exchange private static void swap (int [] data, int i, int j) {int TMP = data [i]; data [i] = data [J]; data [J] = TMP;}}
//Insert sort algorithm stable public class insertsort{
public static void main(String[] args) {
int[] a={49,64,1};
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.print(a[i]+" ");
}
//直接插入排序
for (int i = 1; i < a.length; i++) {
//待插入元素
int temp = a[i];
int j;
/*for (j = i-1; j>=0 && a[j]>temp; j--) {
//将大于temp的往后移动一位
a[j+1] = a[j];
}*/
for (j = i-1; j>=0; j--) {
//将大于temp的往后移动一位
if(a[j]>temp){
a[j+1] = a[j];
}else{
break;
}
}
a[j+1] = temp;
}
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println();
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.print(a[i]+" ");
}
}}
//Merge sort stable public class mergsort {public static void main (string [] args) {int [] a = {49,1,8}; System. out. Println ("before sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } // Merge sort (a, a. length-1); System. out. println(); System. out. Println ("after sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } }
private static void mergeSort(int[] a,int left,int right) {
if(left<right){
int middle = (left+right)/2;
//对左边进行递归
mergeSort(a,left,middle);
//对右边进行递归
mergeSort(a,middle+1,right);
//合并
merge(a,middle,right);
}
}
private static void merge(int[] a,int middle,int right) {
int[] tmpArr = new int[a.length];
int mid = middle+1; //右边的起始位置
int tmp = left;
int third = left;
while(left<=middle && mid<=right){
//从两个数组中选取较小的数放入中间数组
if(a[left]<=a[mid]){
tmpArr[third++] = a[left++];
}else{
tmpArr[third++] = a[mid++];
}
}
//将剩余的部分放入中间数组
while(left<=middle){
tmpArr[third++] = a[left++];
}
while(mid<=right){
tmpArr[third++] = a[mid++];
}
//将中间数组复制回原数组
while(tmp<=right){
a[tmp] = tmpArr[tmp++];
}
}}
//Bubble sort stable public class MP {public static void main (string [] args) {int [] a = {49,8}; System. out. Println ("before sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } // Bubble sort for (int i = 0; I < a.length; I + +) {for (int j = 0; J < a.length-i-1; j + +) {/ / here - I mainly sinks the maximum I number to the bottom every traversal. There is no need to replace if (a [J] > a [J + 1]) {int temp = a [J]; a [J] = a [J + 1]; a [J + 1] = temp;}}}} System. out. println(); System. out. Println ("after sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }
//Unstable fast exhaust public class quicksort {public static void main (string [] args) {int [] a = {49,8}; System. out. Println ("before sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } // Quick sort (a); System. out. println(); System. out. Println ("after sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } }
private static void quick(int[] a) {
if(a.length>0){
quickSort(a,a.length-1);
}
}
private static void quickSort(int[] a,int low,int high) {
if(low<high){ //如果不加这个判断递归会无法<a href="https://www.jb51.cc/tag/tuichu/" target="_blank" class="keywords">退出</a>导致堆栈溢出异常
int middle = getMiddle(a,low,high);
quickSort(a,middle-1);
quickSort(a,high);
}
}
private static int getMiddle(int[] a,int high) {
int temp = a[low];//基准元素
while(low<high){
//找到比基准元素小的元素位置
while(low<high && a[high]>=temp){
high--;
}
a[low] = a[high];
while(low<high && a[low]<=temp){
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}}
//Cardinality sorting stable import Java util. ArrayList; import java. util. List;
public class RaSort { public static void main(String[] args) { int[] a={49,176,213,227,164,11,18,1}; System. out. Println ("before sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } // Cardinality sort (a); System. out. println(); System. out. Println ("after sorting:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } }
@SuppressWarnings({ "rawtypes","unchecked" })
private static void sort(int[] array) {
//找到最大数，确定要排序几趟
int max = 0;
for (int i = 0; i < array.length; i++) {
if(max<array[i]){
max = array[i];
}
}
//判断位数
int times = 0;
while(max>0){
max = max/10;
times++;
}
//建立十个队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList queue1 = new ArrayList();
queue.add(queue1);
}
//进行times次分配和收集
for (int i = 0; i < times; i++) {
//分配
for (int j = 0; j < array.length; j++) {
int x = array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
ArrayList queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x,queue2);
}
//收集
int count = 0;
for (int j = 0; j < 10; j++) {
while(queue.get(j).size()>0){
ArrayList<Integer> queue3 = queue.get(j);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}}
//Unstable selection sort public class selectsort{
public static void main(String[] args) {
int[] a={49,8};
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.print(a[i]+" ");
}
//简单的选择排序
for (int i = 0; i < a.length; i++) {
int min = a[i];
int n=i; //最小数的索引
for(int j=i+1;j<a.length;j++){
if(a[j]<min){ //找出最小的数
min = a[j];
n = j;
}
}
a[n] = a[i];
a[i] = min;
}
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println();
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank" class="keywords">stem</a>.out.print(a[i]+" ");
}
}}