heyheyhey ~~
It has been a long time since i come here again...whatever today i will summerize some methods of sort with java what are so important for coder. The codes below are all compiled successfully and have the right results
一. insert sort -- is divided into insert directly and Shell Sort.
1. insert directly -- the main idea is while obtaining a new value, to compare the new value with the number of sorted array, when get the position that the value is lager than the front number and smaller than the behind number, insert the value.
public class InsertDirectly {
public static void insertDirectly(int[] a) {
for(int i = 1; i<a.length; ++i) {
// because maybe the insert value would be complicanted , so we should define a copy for it
int temp = a[i];
// then go through the every number of the sorted array to find out the right position.
// to make the j be the global variable.
int j = i-1
// because maybe the a[i] would be complicanted, so a[j] shouled > temp,not a[i]
for(; j >= 0 && a[j] > temp; --j) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
2. Shell Sort is the special sort of insert sort, just because it has the increment-'d' ,not one ny one any more.
main idea is just according to the 'd' to carry out the method of directly insert sort
public class ShellSort{
public static void shellSort(int[] a) {
// firt step ：need to init the 'd'.
double d1 = a.length;
// the 'd' need to be changed, so make sure the loop
while(true) {
//ceil -- get the bigger one
double d1 = Math.ceil(d1/2);
int d = (int) d1;
// for the outer loop
for(int i = 0; i<d; ++i) {
//for the increment loop
for(int j = i+d; j < a.length; i+=d) {
int temp = a[j];
// for the inner loop
int x = j-d;
for(; x >= 0 && a[x] > temp; x-=d) {
a[x+d] = a[x];
}
a[x+d] = temp;
}
}
if( d == 1) break;
}
}
}
二. select sort -- is divided into easy select sort and heap sort.
1. easy select sort is the most easy sort -- main idea is make sure the loop of find out the lagest one or the smallest one ,and put it to the rear or head of the array
public class EasySort {
public static void swap(int[] a ,int x, int y) {
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public static void easySort(int[] a) {
for(int i = 0; i<a.length; ++i) {
int max = a[i];
int flag = i;
for(int j = i+1; j < a.length;++j) {
if(max < a[j]) {
max = a[j];
flag = j;
}
}
swap(a, a.length-1-i, flag);
}
}
}
2.Heap Sort is actually the selected sort based on heap -- main idea is that build max or min heap and then change the position bettween the max or min and the last position.
public class HeapSort {
// this methid is mainly to change the max value which is in the top of heap(in other word which is always the first position of the array)
// with the last number of this array.
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void heapSort(int[] a) {
// from the last value of the array in order to buildMaxHeap circularly.
for(int i = a.length-1; i > 0; --i) {
buildMaxHeap(a, i);
swap(a, 0, i);
}
}
// next is the highlight of the heap sort ,and in this method we would to let u know how to bulid the max heap and how to reform the heap a
// again and again.
public static void buildMaxHeap(int[] a,int lastIndex) {
// step 1 : get the last father node of this heap
int lastFather = (lastIndex-1)/2;
// step 2 : we need to find out the max value among the father node and the subnodes
for(int i = lastFather; i >= 0; --i) {
// step 2.1 : first we need to find out the max value bettween the subnodes
int biggerIndex = lastFather*2+1; // make the left node be the max first and then judge if the right node exists
if(biggerIndex < lastIndex) // make sure the right node exists {
if(a[biggerIndex] < a[lastIndex]) {
biggerIndex ++;
}
}
// step 2.2 : second we need to compare the biggerOne and the father node
if(a[lastFather] < a[biggerIndex]) {
// let the larger value go to the top
swap(a, lastFather, biggerIndex);
}
}
}
}