各种排序算法之Java实现
排序算法有一个基本的交换步骤，所以我提取这个基本步骤到父类，父类中同时也加入打印输出这个功能以便查看排序结果排序算法的父类代码如下
public class SortBase {protected void swap(int[] array, int i, int j) {int temp;temp = array;array = array;array = temp;}protected void printArray(int[] array) {for (int i : array) {System.out.print(i + " ");}}}
(1) 冒泡排序
public class BubbleSort extends SortBase {// 冒泡是一种简单的交换排序public void bubbleSort(int[] array) {for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - i - 1; j++)if (array < array)// 小的往上冒,由大到小swap(array, j, j + 1);}}
(2) 插入排序
//复杂度平方阶public class InsertSort extends SortBase {// 直接插入排序,默认第一个有序，然后像打扑克那样插入public void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {for (int j = 0; j < i; j++) {if (array < array)swap(array, i, j);// 使用交换技术，也可依次后移}}}//另外一种实现,见shell插入部分public void insertionSort(int[] a) {for (int p = 1; p < a.length; p++) {int tmp = a;int j = p;for (; j > 0 && tmp<a; j--)a = a;//如果小就往后移动a = tmp;//将待插入元素插到移动完的空位处}}}
(3) 选择排序
//复杂度，平方阶public class SelectSort extends SortBase {// 直接选择排序，先默认第一个最大，然后在后面的序列中找出比他大的来交换，这样不停的重复public void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int max_potion = i;for (int j = i + 1; j < array.length; j++)if (array < array)max_potion = j;if (i != max_potion)// 如果默认失效swap(array, i, max_potion);}}}
(4) 快速排序
//复杂度平方阶，平均是线性对数public class QuickSort extends SortBase {// 快速排序时获取轴点public int partition(int[] array, int low, int high) {int compare = array;// 和最后一个high比较int i = low - 1;for (int j = low; j < high; j++)// 扫描high之前的所有数据，把比high大的全部按顺序从低位排列if (array > compare)swap(array, ++i, j);swap(array, ++i, high);// 将high处的值插入比他大的所有数据之后，这样就取到了轴点return i;}// 对冒泡的改进，快速排序,原理就是递归的分段，左端----轴点----右端,左<轴<右，或者左>轴>右public void quickSort(int[] array, int low, int high) {if (low < high) {int pivot = partition(array, low, high);quickSort(array, low, pivot - 1);quickSort(array, pivot + 1, high);}}}
(5) 希尔排序
//希尔排序 O(n的1.x次方)public class ShellSort {//按照增量进行直接插入public void shellInsert(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int temp = array;int j = i;for (; j >= gap && temp > (array); j -= gap)array = array;array = temp;}}public void shellSort(int[] array) {for (int gap = array.length / 2; gap > 0; gap /= 2)//取增量shellInsert(array, gap);}}
(6) 归并排序
//归并排序 分而治之,分解再合并，map reduce?public class MergeSort extends SortBase {public void mergeSort(int[] a) {int[] tmpArray = new int;mergeSort(a, tmpArray, 0, a.length - 1);}//分割privatevoid mergeSort(int[] a, int[] tmpArray, int left, int right) {if (left < right) {int center = (left + right) / 2;mergeSort(a, tmpArray, left, center);mergeSort(a, tmpArray, center + 1, right);merge(a, tmpArray, left, center + 1, right);}}//归并privatevoid merge(int[] a, int[] tmpArray, int leftPos,int rightPos, int rightEnd) {int leftEnd = rightPos - 1;int tmpPos = leftPos;int numElements = rightEnd - leftPos + 1;// Main loopwhile (leftPos <= leftEnd && rightPos <= rightEnd)if (a <= (a))tmpArray = a;elsetmpArray = a;while (leftPos <= leftEnd)// Copy rest of first halftmpArray = a;while (rightPos <= rightEnd)// Copy rest of right halftmpArray = a;// Copy tmpArray backfor (int i = 0; i < numElements; i++, rightEnd--)a = tmpArray;}public static void main(String args[]){int a[] = {9,8,6,7,5,4,3,2,1,0};new MergeSort().mergeSort(a);new MergeSort().printArray(a);}}
(7) 堆排序
//堆排序,复杂度是线性对数,是一种树形选择排序public class HeapSort extends SortBase {public void heapsort(int[] a) {for (int i = a.length / 2; i >= 0; i--)percDown(a, i, a.length);//从层次最高的非叶子节点开始建堆，这样从下到上，就可以利用堆的性质，可做部分记忆for (int i = a.length - 1; i > 0; i--) {swap(a, 0, i); //每次调整都把最大或者最小输出到了a处，把它交换到最后percDown(a, 0, i);}}private int leftChild(int i) {return 2 * i + 1;}private void percDown(int[] a, int i, int n) {int child;int tmp;for (tmp = a; leftChild(i) < n; i = child) {child = leftChild(i);if (child != n - 1 && a < a)//比较左右节点child++;if (tmp < a)a = a;//把从左右节点选出来的值赋值到根elsebreak;}a = tmp;}public static void main(String args[]){int a[] ={0,5,4,3,2,1,10,-1};new HeapSort().heapsort(a);new HeapSort().printArray(a);}}
页:
[1]