Java 다양한 정렬
11104 단어 데이터 구조와 알고리즘
package com.sbw.testredis;
import java.util.Arrays;
public class Sort{
// o(n^2)
public void bubbleSort(int[] data){
boolean isSort = true;
for(int i = 0; i < data.length - 1 && isSort; i++){
isSort = false;
for(int j = data.length - 1; j > i; j--){
if(data[j-1] > data[j]){
int temp = data[j-1];
data[j-1] = data[j];
data[j] =temp;
isSort = true;
}
}
}
}
// o(n^2)
public void chooseSort(int[] data){
int min = 0;
for(int i = 0; i < data.length - 1; i++){
min = i;
for(int j = i + 1; j < data.length; j++){
if(data[j] < data[min]){
min = j;
}
}
if(min != i){
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
}
// o(n^2)
public void insertSort(int[] data){
int i,j;
for(i = 1; i < data.length; i++){
if(data[i] < data[i-1]){
int temp = data[i];
for(j = i - 1; j >=0 && data[j] > temp; j--){
data[j+1] = data[j];
}
data[j+1] = temp;
}
}
}
// o(nlogn)
public void heapSort(int[] data){
int length = data.length;
for(int i = length/2 - 1; i >= 0; i--)
buildMaxHeap(i, length, data);
for(int i = length - 1; i > 0; i--){
int temp = data[i];
data[i] = data[0];
data[0] = temp;
buildMaxHeap(0, i, data);
}
}
private void buildMaxHeap(int nodeIndex, int length, int[] data){
int temp = data[nodeIndex];
for(int i = 2 * nodeIndex + 1; i < length; i = 2 * i + 1){
if(i < length - 1 && data[i] < data[i+1])
i++;
if(temp >= data[i])
break;
data[nodeIndex] = data[i];
nodeIndex = i;
}
data[nodeIndex] = temp;
}
// o(nlogn) o(logn)
public void quickSort(int[] data){
_quickSort(data, 0, data.length - 1);
}
private void _quickSort(int[] data, int left, int right){
if(left < right){
int middle = getMiddle(data, left, right);
_quickSort(data, left, middle - 1);
_quickSort(data, middle + 1, right);
}
}
private int getMiddle(int[] data, int left, int right){
int pivot = data[left];
while(left < right){
while(left < right && data[right] >= pivot)
right--;
if (left < right)
data[left++] = data[right];
while (left < right && data[left] <= pivot)
left++;
if (left < right)
data[right--] = data[left];
}
data[left] = pivot;
return left;
}
// o(nlogn) o(n)
public void mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private void internalMergeSort(int[] a, int[] b, int left, int right){
if (leftint middle = (left+right)/2;
internalMergeSort(a, b, left, middle);
internalMergeSort(a, b, middle+1, right);
mergeSortedArray(a, b, left, middle, right);
}
}
private void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while (i <= middle && j <= right){
if (arr[i] <= arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
while (i <= middle){
temp[k++] = arr[i++];
}
while (j <= right){
temp[k++] = arr[j++];
}
//
for (i = 0; i < k; i++){
arr[left+i] = temp[i];
}
}
public static void main(String[] args){
int[] data = {3,34,123,4,45,67,564,789,5,675};
Sort test = new Sort();
//test.bubbleSort(data);
//test.chooseSort(data);
//test.insertSort(data);
//test.heapSort(data);
//test.quickSort(data);
test.mergeSort(data);
System.out.println(Arrays.toString(data));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.