ソートアルゴリズム要約Java
1、泡立ち順
2、ソートの選択
3、ソートの挿入
4、ヒルソート
5、集計ソート
6、クイックソート
7、スタックの順序付け
8、カウントソート
参照先:https://www.cnblogs.com/guoyaohua/p/8600214.html https://segmentfault.com/a/1190000014105591 https://tryenough.com/arithmetic-quitsort https://www.cnblogs.com/developerY/p/3166462.html https://blog.csdn.net/zdp072/article/details/44227317
/* ：
1、 ， ， ；
2、 ， ， ；
3、 ， ；
4、 。*/
import java.util.Scanner;
public class bubbleSort {
public static int[] sort(int[] array) {
if(array.length == 0) {
return array;
}
int temp = 0;
for(int i = 0; i < array.length; i ++) {
for(int j = 0; j < array.length - i - 1; j ++) {
if(array[j] > array[j + 1]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n ; i ++) {
arr[i] = sc.nextInt();
}
for(int j = 0; j < n ; j ++) {
System.out.print(sort(arr)[j] + ",");
}
}
}
2、ソートの選択
package paixu;
/* ：
1、 ， ；
2、n-1 ， 。*/
public class selectionSort {
public static int[] sort(int[] array) {
if(array.length == 0) {
return array;
}
for(int i = 0; i < array.length; i ++) {
int minIndex = i;
for(int j = i; j < array.length ; j ++) {
if(array[minIndex] > array[j]) {
int temp = array[minIndex];
array[minIndex] = array[j];
array[j] = temp;
}
}
}
return array;
}
public static void main(String args[]) {
int[] arr = new int[] {7,1,5,9,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr)[i] + ",");
}
}
}
3、ソートの挿入
package paixu;
/* ：
， ， 。
1、 ， ；
2、 ， ， ， ；
3、 2。*/
public class insertionSort {
public static int[] sort(int[] array) {
if(array.length == 0) {
return array;
}
for(int i = 0; i < array.length - 1; i ++) {
int preIndex = i;
int current = array[i + 1];
while(preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex --;
}
array[preIndex + 1] = current;
}
return array;
}
public static void main(String args[]) {
int[] arr = new int[] {7,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr)[i] + ",");
}
}
}
4、ヒルソート
package paixu;
/* ：
， gap=len/2，gap=len/2/2，...*/
public class shellSort {
public static int[] sort(int[] array) {
if(array.length == 0) {
return array;
}
int len = array.length;
int gap = len / 2;
while(gap > 0) {
for(int i = 0; i < len - gap; i ++) {
int current = array[i + gap];
int preIndex = i;
while(preIndex >= 0 && array[preIndex] > current) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = current;
}
gap = gap >> 1;
}
return array;
}
public static void main(String[] args) {
int[] arr = new int[] {7,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr)[i] + ",");
}
}
}
5、集計ソート
package paixu;
import java.util.Arrays;
/* ：
*/
public class mergeSort {
public static int[] sort(int[] array) {
if(array.length < 2) {
return array;
}
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(sort(left),sort(right));
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
int j = 0;
for(int index = 0; index < result.length; index ++) {
if(i >= left.length) {// result
result[index] = right[j];
j ++;
}else if(j >= right.length){
result[index] = left[i];
i ++;
}else if(left[i] > right[j]) {// result
result[index] = right[j];
j ++;
}else {
result[index] = left[i];
i ++;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = new int[] {7,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr)[i] + ",");
}
}
}
6、クイックソート
package paixu;
import java.util.Arrays;
/* ：
，
， ， 。
1、 ， ；
2、 ， ， ；
3、 2， 。
*/
public class quickSort {
public static int[] sort(int[] array, int start, int end) {
if(array.length == 0 || start >= end) {
return array;
}
int pivot = array[start];//
int left = start; //
int right = end;//
while(left < right) {
// ,
while(left < right && array[right] > pivot) {
right --;
}
if(left < right) {
array[left] = array[right];//
left ++;//
}
// ,
while(left < right && array[left] < pivot) {
left ++;
}
if(left < right) {
array[right] = array[left];//
right --;//
}
}
array[left] = pivot;// left
sort(array, start, left - 1);// ，
sort(array, left + 1, end);// ，
return array;
}
public static void main(String[] args) {
int[] arr = new int[] {8,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr, 0 , arr.length - 1)[i] + ",");
}
}
}
7、スタックの順序付け
package paixu;
/* ：
（ ， ），
。
( ， )，
n-1 ， n 。
， 。
*/
public class heapSort {
public static int[] sort(int[] array) {
if(array.length == 0) {
return array;
}
//
for(int i = array.length / 2; i >= 0; i --) {
heapAdjust(array, i, array.length);
}
// ， ，
for(int i = array.length - 1; i > 0; i --) {
swap(array,0,i); //
heapAdjust(array, 0, i);// ， ，
}
return array;
}
// ，
public static void heapAdjust(int[] array, int i, int n) {
int child;
int father;
for(father = array[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
// ，
if(child != n -1 && array[child] < array[child + 1]) {
child ++;// 1，
}
// ，
if(father < array[child]) {
array[i] = array[child];
}else {
break;// ，
}
}
array[i] = father;
}
//
public static int leftChild(int i) {
return 2 * i + 1;
}
//
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void main(String[] args) {
int[] arr = new int[] {8,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr)[i] + ",");
}
}
}
8、カウントソート
package paixu;
/* ：
1、 A ；
2、 A i ， C i ；
3、 C i C i ；
4、 A B， A ， C， B ，
C -1（ ， ，
）。
*/
public class countingSort {
public static int[] sort(int[] array, int k) {
if(array.length == 0) {
return array;
}
int sum = 0;
int[] B = new int[array.length];
int[] C = new int[k + 1];
for(int i = 0; i < array.length; i ++) {
C[array[i]] += 1;// A ， C
}
for(int i = 0; i < k+1; i ++) {// C
sum += C[i];
C[i] = sum;
}
for(int i = array.length - 1; i >= 0; i--) {// A， B
B[C[array[i]]- 1] = array[i];// A B
C[array[i]] --;// C -1，
}
return B;
}
public static void main(String[] args) {
int[] arr = new int[] {8,1,5,6,3,2};
for(int i = 0; i < arr.length; i ++) {
System.out.print(sort(arr, 8)[i] + ",");
}
}
}
参照先:https://www.cnblogs.com/guoyaohua/p/8600214.html https://segmentfault.com/a/1190000014105591 https://tryenough.com/arithmetic-quitsort https://www.cnblogs.com/developerY/p/3166462.html https://blog.csdn.net/zdp072/article/details/44227317