ソートjava実装
5513 ワード
package datastructure;
import java.util.Arrays;
// sort from small to big
public class Sort {
//
public void selectionSort(int[] array) {
int length = array.length;
int tempValue = 0;
int tempIndex = 0;
for (int i = 0; i < length - 1; i++) {
tempValue = array[i];
tempIndex = i;
for (int j = i; j < length; j++) {
if (array[j] < tempValue) {
tempValue = array[j];
tempIndex = j;
}
}
array[tempIndex] = array[i];
array[i] = tempValue;
}
}
//
public void insertSort(int[] array) {
int tempValue = 0;
int length = array.length;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (array[i] < array[j]) {
tempValue = array[i];
for (int k = i; k > j; k--) {
array[k] = array[k - 1];
}
array[j] = tempValue;
}
}
}
}
//
public void bubbleSort(int[] array) {
int length = array.length;
int tempValue = 0;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
tempValue = array[j];
array[j] = array[j + 1];
array[j + 1] = tempValue;
}
}
}
}
//
public int[] mergeSort(int[] arrs) {
if(arrs.length < 2){
return arrs;
}
int middle = arrs.length % 2 == 0 ? arrs.length / 2 : (arrs.length - 1) / 2;
int[] left = Arrays.copyOfRange(arrs, 0, middle);
int[] right = Arrays.copyOfRange(arrs, middle, arrs.length);
int[] lres = mergeSort(left);
int[] rres = mergeSort(right);
return merge(lres, rres);
}
private int[] merge(int[] lres, int[] rres) {
int[] res = new int[lres.length + rres.length];
int l = 0;
int r = 0;
int c = 0;
while(l < lres.length && r < rres.length){
if(lres[l] < rres[r]){
res[c++] = lres[l++];
} else {
res[c++] = rres[r++];
}
}
if(l == lres.length){
while(r < rres.length){
res[c++] = rres[r++];
}
return res;
}
if(r == rres.length){
while(l < lres.length){
res[c++] = lres[l++];
}
return res;
}
return res;
}
//
public void quickSort(int[] array, int i, int j) {
if (i < j) {
int start = i;
int end = j;
int partition = array[i];
while (i < j) {
while (i<j && partition <= array[j]) {
j--;
}
array[i] = array[j];
while(i<j && partition >= array[i]){
i++;
}
array[j] = array[i];
}
array[i] = partition;
this.quickSort(array, start, i-1);
this.quickSort(array, i + 1, end);
}
}
//
public void heapSort(int[] array) {
this.createHeap(array);
int heapLength = array.length;
for (int i=0;i<array.length;i++) {
int temp = array[heapLength-1];
array[heapLength-1]=array[0] ;
array[0] = temp;
heapLength=heapLength-1;
this.heapifyDown(array, 0, heapLength);
}
}
private void createHeap(int[] array){
int length = array.length;
for (int i=length/2-1; i>=0; i--) {
this.heapifyDown(array, i, length);
}
}
// arraylen , ,heap size 。 heapifydown ,
private void heapifyDown(int[] array, int i, int arraylen){
//int length = array.length;
int length = arraylen;
if (2*i+2 > length)
return;
if (2*i+2 == length) {
if(array[i] > array[length-1]){
int temp = array[i];
array[i] = array[length-1];
array[length-1] = temp;
}
} else {
int compareIndex;
if (array[2*i+1]<array[2*i+2])
compareIndex = 2*i+1;
else
compareIndex = 2*i+2;
if(array[i] > array[compareIndex]) {
int temp = array[i];
array[i] = array[compareIndex];
array[compareIndex] = temp;
this.heapifyDown(array, compareIndex, length);
}
}
}
public void print(int[] array) {
int len = array.length;
for (int i = 0; i < len; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = (int) (Math.random() * 100);
}
Sort s = new Sort();
System.out.println("Before sorting:");
s.print(array);
// s.selectionSort(array);
// s.insertSort(array);
// s.bubbleSort(array);
//s.quickSort(array, 0, n - 1);
//s.heapSort(array);
s.print(s.mergeSort(array));
System.out.println("After sorting:");
s.print(array);
}
}