8つの並べ替えアルゴリズムJavaを実装します。
18301 ワード
図解ソートアルゴリズム:
http://blog.csdn.net/middlekingt/article/details/8425686
java実現コード：
http://blog.csdn.net/middlekingt/article/details/8425686
java実現コード：
package com.algorithm;
/*
* java
*/
public class Sort
{
//
private final static int MAX_SIZE = 10;
@SuppressWarnings("static-access")
public static void main(String[] args)
{
//
int[] bef_sort = new int[MAX_SIZE];
//
for(int i=0;iint)(100+Math.random()*(100+1));
}
System.out.println(" ： ");
println(bef_sort);
System.out.println(" ： ");
//
// new Mao_sort().sort(bef_sort);
//
// new Select_sort().sort(bef_sort);
//
// new Insert_sort().sort(bef_sort);
//
// new Shell_sort().sort(bef_sort);
//
// new Quick_sort().sort(bef_sort);
//
// new Merging_Sort().sort(bef_sort, 0, bef_sort.length-1);
//
// new RadixSort().sort(bef_sort, bef_sort.length);
//
new HeapSort().heapSort(bef_sort);
println(bef_sort);
}
public static void println(int[] bef_sort){
// ：
for (int i = 0; i < bef_sort.length; i++)
{
System.out.print(bef_sort[i]+",");
}
System.out.println();
}
}
/*
* ：
* ，
*/
class Mao_sort{
public static void sort(int[] a){
int temp;
for(int i=1;ifor(int j=0;jif(a[j]>a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
}
/*
* ：
*
*
*/
class Select_sort{
public static void sort(int[] a){
//
int index;
int temp;
for(int i=0;i1;i++){
index = i;
for(int j=1;jif(a[j]if(index！=i){
temp=a[i];
a[i]=a[index]
a[index]=temp;
)
)
)
)
/*
* べ えの :
* の2つの サイズを べ え、3 の を に し、 のクラスを じにします。
*/
class Insert_sort{
public void sort(int[]a){
//2つの を し、 と をそれぞれ します。
int index、temp
for(int i=1;i1;
temp = a[i];
while(index>=0 && a[index]>temp){
a[index+1] = a[index];
index--;
}
a[index+1] = temp;
}
}
}
/*
* Shell
* n n/2 ， 1 n/2+1
*
*/
class Shell_sort{
public void sort(int[] sort_shell){
int j,temp;
int i,r;
for(r=sort_shell.length/2;r>=1;r/=2){
for (i = r; i < sort_shell.length; i++)
{
temp =sort_shell[i];
j = i - r;
while(j>=0 && sort_shell[j]>temp){
sort_shell[j+r] = sort_shell[j];
j-=r;
}
sort_shell[j+r] = temp;
}
}
}
}
//
class Quick_sort{
public void sort(int[] arr){
quick_sort(arr, 0, arr.length-1);
}
//
public int getMiddle(int[] arr,int low ,int high){
int temp = arr[low];
while(lowwhile(low=temp){
high--;
}
arr[low] = arr[high];
while(lowreturn low;
}
public void quick_sort(int[] arr,int low,int high){
if(lowint middle = getMiddle(arr, low, high);
quick_sort(arr, low, middle-1);
quick_sort(arr, middle+1, high);
}
}
}
/*
*
* （ ） ，
* ， ，
* 。
* O(nlogn)
*
* @param nums
* @return
*/
class Merging_Sort{
public void sort(int[] a,int left,int right){
//
int center = (left+right)/2;
if(left//
sort(a, left, center);
//
sort(a, center+1, right);
//
merge(a, left, center, right);
}
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;//
int j = mid + 1;//
int k = 0;
//
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
//
while (i <= mid) {
temp[k++] = nums[i++];
}
//
while (j <= high) {
temp[k++] = nums[j++];
}
// nums
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
}
/*
*
* : “ ”, , ， “ ” ，
* O (nlog(r)m)， r ， m
*
* @param nums
* @d
*/
class RadixSort{
public static void sort(int[] nums,int d){
int k = 0;
int n = 1;
int len = nums.length;
// nums.length
int[][] radixArray = new int[len][len];
//
int[] tempArray = new int[len];
//
while (n<=d) {
for (int i = 0; i < len; i++) {
// , , , ...
int temp = (nums[i]/n)%10;
//
radixArray[temp][tempArray[temp]] = nums[i];
tempArray[temp]++;
}
for (int i = 0; i < len; i++) {
if (tempArray[i] != 0) {
for (int j = 0; j < tempArray[i]; j++) {
//
nums[k] = radixArray[i][j];
k++;
}
// ,
tempArray[i] = 0;
}
}
// ,
k = 0;
//
n *=10;
}
}
}
/*
* ：
* ， , ，
* i(Java 0 ,i 0 n-1),
* ， 2i+1， ， 2i+2，
* ， (n-1)/2 。
* ， ， 。
* ， 。
* ， ， ， 。
* 0 ， ， 0 。
* ( ), O(n2)， 。
*/
/*
* :
* 1、 。
* 2、 ， 0
* 3、 2 ， 0 ， maxHeap ( )， 2
*
* maxHeap， ( )，
* ， ，
* ， ， ， ，
* maxHeap 。 。
* :
*
*/
class HeapSort {
public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
buildMaxHeap(array);
for (int i = array.length - 1; i >= 1; i--) {
exchangeElements(array, 0, i);
maxHeap(array, i, 0);
}
}
private static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int half = array.length / 2;
for (int i = half; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}
private static void maxHeap(int[] array, int heapSize, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (index != largest) {
exchangeElements(array, index, largest);
maxHeap(array, heapSize, largest);
}
}
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}