package com.meteor.algorithm;
/**
* sortMethods
* Created by Meteor on 2016/3/26.
*/
public class SortMethods {
/**
* Simple insertionSort(插入排序)
* @param arr the array that need to sort
* @param <T> type parameter
*/
public static <T extends Comparable<? super T>> void insertionSort(T [] arr){
int j;
for(int p = 1;p < arr.length;p++){
T tmp = arr[p];
for(j = p;j > 0 && tmp.compareTo(arr[j-1])<0;j--){
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
/**
* quicksort(快速排序)
* @param arr an array of Comparable items
* @param left the left-most index of the subarray
* @param rignt the right-most index of the subarray
* @param <T>
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr,int left,int rignt){
int dp;
if(left < rignt){
dp = partition(arr,left,rignt);
quicksort(arr,left,dp-1);
quicksort(arr,dp+1,rignt);
}
}
private static <T extends Comparable<? super T>> int partition(T[] arr,int left,int right ){
T centerValue = arr[left];
while (left < right){
while (left < right && (arr[right].compareTo(centerValue))>0){
right--;
}
if(left<right){
arr[left++] = arr[right];
}
while (left < right && (arr[left].compareTo(centerValue))<0){
left++;
}
if(left<right){
arr[right--] = arr[left];
}
}
arr[left] = centerValue;
return left;
}
/**
* shellSort(希尔排序)
* @param arr
* @param <T>
*/
public static <T extends Comparable<? super T>> void shellSort(T [] arr){
int j;
for(int gap = arr.length/2;gap > 0;gap /= 2){
for(int i = gap;i<arr.length;i++){
T tmp = arr[i];
for(j = i;j >= gap && tmp.compareTo(arr[j-gap]) < 0; j -=gap){
arr[j] = arr[j-gap];
}
arr[j] = tmp;
}
}
}
/**
* Mergesort algotithm(归并排序)
* @param arr an array of Comparable items
* @param <T>
*/
public static <T extends Comparable<? super T>> void mergeSort(T[] arr){
T[] tempArr = (T[]) new Comparable[arr.length];
mergeSort(arr,tempArr,0,arr.length-1);
}
/**
* Internal method that makes recursive calls
* @param arr an array of Comparable items
* @param tempArr an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
* @param <T>
*/
private static <T extends Comparable<? super T>>
void mergeSort(T[] arr,T[] tempArr,int left,int right){
if(left < right){
int center = (left+right)/2;
mergeSort(arr,tempArr,left,center);
mergeSort(arr,tempArr,center+1,right);
merge(arr,tempArr,left,center+1,right);
}
}
/**
* Internal method that merges two sorted halves of a subarray
* @param arr a array of Comparable items
* @param tempArr an array to place the merged result
* @param leftPos the left-most index of the subarray
* @param rightPos the index of the start of the second half
* @param rightEnd the right-most index of the subarray
* @param <T>
*/
private static <T extends Comparable<? super T>> void merge(T [] arr,T [] tempArr, int leftPos, int rightPos,int rightEnd){
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd){
if(arr[leftPos].compareTo(arr[rightPos]) <= 0){
tempArr[tmpPos++] = arr[leftPos++];
}else{
tempArr[tmpPos++] = arr[rightPos++];
}
}
//copy rest of first half
while (leftPos <= leftEnd){
tempArr[tmpPos++] = arr[leftPos++];
}
//copy rest of right half
while (rightPos<=rightEnd){
tempArr[tmpPos++] = arr[rightPos++];
}
//copy tempArr back
for (int i = 0; i < numElements ; i++,rightEnd--) {
arr[rightEnd] = tempArr[rightEnd];
}
}
public static void main(String[] args) {
Integer [] arr = {10,19,12,14,9,6,3,45};
//SortMethods.insertionSort(arr);
SortMethods.shellSort(arr);
for (Integer tem:arr){
System.out.print(tem+"; ");
}
}
}
package com.meteor.algorithm;
/**
* sortMethods
* Created by Meteor on 2016/3/26.
*/
public class SortMethods {
/**
* Simple insertionSort(插入排序)
* @param arr the array that need to sort
* @param <T> type parameter
*/
public static <T extends Comparable<? super T>> void insertionSort(T [] arr){
int j;
for(int p = 1;p < arr.length;p++){
T tmp = arr[p];
for(j = p;j > 0 && tmp.compareTo(arr[j-1])<0;j--){
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
/**
* quicksort(快速排序)
* @param arr an array of Comparable items
* @param left the left-most index of the subarray
* @param rignt the right-most index of the subarray
* @param <T>
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr,int left,int rignt){
int dp;
if(left < rignt){
dp = partition(arr,left,rignt);
quicksort(arr,left,dp-1);
quicksort(arr,dp+1,rignt);
}
}
private static <T extends Comparable<? super T>> int partition(T[] arr,int left,int right ){
T centerValue = arr[left];
while (left < right){
while (left < right && (arr[right].compareTo(centerValue))>0){
right--;
}
if(left<right){
arr[left++] = arr[right];
}
while (left < right && (arr[left].compareTo(centerValue))<0){
left++;
}
if(left<right){
arr[right--] = arr[left];
}
}
arr[left] = centerValue;
return left;
}
/**
* shellSort(希尔排序)
* @param arr
* @param <T>
*/
public static <T extends Comparable<? super T>> void shellSort(T [] arr){
int j;
for(int gap = arr.length/2;gap > 0;gap /= 2){
for(int i = gap;i<arr.length;i++){
T tmp = arr[i];
for(j = i;j >= gap && tmp.compareTo(arr[j-gap]) < 0; j -=gap){
arr[j] = arr[j-gap];
}
arr[j] = tmp;
}
}
}
/**
* Mergesort algotithm(归并排序)
* @param arr an array of Comparable items
* @param <T>
*/
public static <T extends Comparable<? super T>> void mergeSort(T[] arr){
T[] tempArr = (T[]) new Comparable[arr.length];
mergeSort(arr,tempArr,0,arr.length-1);
}
/**
* Internal method that makes recursive calls
* @param arr an array of Comparable items
* @param tempArr an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
* @param <T>
*/
private static <T extends Comparable<? super T>>
void mergeSort(T[] arr,T[] tempArr,int left,int right){
if(left < right){
int center = (left+right)/2;
mergeSort(arr,tempArr,left,center);
mergeSort(arr,tempArr,center+1,right);
merge(arr,tempArr,left,center+1,right);
}
}
/**
* Internal method that merges two sorted halves of a subarray
* @param arr a array of Comparable items
* @param tempArr an array to place the merged result
* @param leftPos the left-most index of the subarray
* @param rightPos the index of the start of the second half
* @param rightEnd the right-most index of the subarray
* @param <T>
*/
private static <T extends Comparable<? super T>> void merge(T [] arr,T [] tempArr, int leftPos, int rightPos,int rightEnd){
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd){
if(arr[leftPos].compareTo(arr[rightPos]) <= 0){
tempArr[tmpPos++] = arr[leftPos++];
}else{
tempArr[tmpPos++] = arr[rightPos++];
}
}
//copy rest of first half
while (leftPos <= leftEnd){
tempArr[tmpPos++] = arr[leftPos++];
}
//copy rest of right half
while (rightPos<=rightEnd){
tempArr[tmpPos++] = arr[rightPos++];
}
//copy tempArr back
for (int i = 0; i < numElements ; i++,rightEnd--) {
arr[rightEnd] = tempArr[rightEnd];
}
}
public static void main(String[] args) {
Integer [] arr = {10,19,12,14,9,6,3,45};
//SortMethods.insertionSort(arr);
SortMethods.shellSort(arr);
for (Integer tem:arr){
System.out.print(tem+"; ");
}
}
}