插入排序

直接插入排序

原理

每一个元素插入它前面排序好的元素中

java实现

//直接插入排序，由小到大 void inserSort( int[] list) { int j; for( int p = 1; p < list.length; p++ ) { int temp = list[p]; //比较当前位置与前面一个的大小， 如果当前位置较小与前一个交换。 for ( j = p; j > 0 && temp - list[ j - 1] < 0; j--) list[j] = list[j-1]; list[j] = temp; } }

希尔排序（缩减增量排序）

原理

对间隔中的数进行直接插入排序排序，间隔慢慢减低，最后到1.

java实现

//希尔排序。（缩减增量排序） void shellsort( int [] a) { int j; for (int gap = a.length /2; gap > 0; gap /= 2) //对每个gap间隔的数组进行直接插入排序 for( int i = gap; i < a.length; i++) { int temp = a[i]; for( j = i; j >= gap && temp - a[j-gap] < 0; j-=gap) a[j] = a[j-gap]; a[j] = temp; } }

堆排序

原理

在本人之前的二叉堆这种数据结构的基础上，进行排序。

java实现

public class HeapSort { //构建小顶堆 public HeapSort( int [] items ) { currentSize = items.length; //确定array'数组'的大小 array = new int[(currentSize + 2) * 11 /10]; sorted = new int[currentSize]; int i = 1; // for xx in list : for( int item : items) //第一个空位留下 array[ i++ ] = item; buildHeap(); } //按由小到大的顺序。排列 public void heapsort() { int i =0; while ( currentSize > 0 ) { sorted[i] = this.deleteMin(); i++; } System.out.println("排序完成"); } public int deleteMin() { int minVal = array[1]; array[1] = array[ currentSize]; currentSize--; percolateDown( 1 ); return minVal; } private int currentSize; private int[] array; //存放排序好的数组 private int[] sorted; // 对于数组任一位置i的元素， 左儿子在2i，右儿子在2i+1， 父在 i/2 private void buildHeap() { for( int i = currentSize /2; i > 0; i-- ) percolateDown( i ); } private void percolateDown( int hole) { int child; int temp = array[ hole ]; for ( ; hole * 2 <= currentSize; hole = child) { child = hole * 2; if ( child != currentSize && array[child + 1] - (array[child]) < 0) child++; if ( array[child]- temp < 0) array[hole] = array[child]; else break; } array[hole] = temp; } }

归并排序

原理

A,B为排序的列表 c为排序好的列表 x,y指向的数进行对比，小的数保存在c中。z和小的个指针更新自己。若A或B那个先用完，将另一个剩下直接放在c中。

java实现

public class MergeSort { public MergeSort(int[] list) { sort(list, 0, list.length - 1); } //递归的将一个大数组转变为小数组 void sort( int[] list, int left, int right) { //递归退出条件 if (left >= right) return; //找出中间索引值 int center = (left + right) /2; sort(list,left, center ); sort(list, center + 1, right ); //合并排序好的数组 merge( list, left, center, right); } //归并, void merge( int[] list, int left, int center, int right ) { int[] tempArray = new int[list.length]; //右数组第一个元素索引 int rightStart = center + 1; //左数组第一个元素的索引 int leftStart = left; // third 记录临时数组的索引 int third = left; while( leftStart <= center && rightStart <= right ) //如果leftPos 处的数《= rightPos处的数， 将leftPos 处的数保存在tempArray中 if (list[leftStart] - list[rightStart] <= 0) tempArray[third++] = list[leftStart++]; else tempArray[third++] = list[rightStart++]; //如果左右俩组数组哪一组先用完 //左组未用完 while ( leftStart <= center ) tempArray[third++] = list[leftStart++]; //右组未用完 while ( rightStart <= right ) tempArray[third++] = list[rightStart++]; //将排序好的数组覆盖原数组 while( left <= right) list[ left ] = tempArray[ left++ ]; } }