一、选择排序
public class SelectSort{ /** *选择排序基本思想： *首先，将一个序列中的最小值与第一个值交换； *第二轮，将剩下n-1个值组成的序列中的最小值与第二个值交换； *直至交换完全。 *时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。 *@param unordered 一个无序列表(为简单起见，假设为整型数组)。 */ public static void main(String[] args) { int test[]={1,3,2,6,4,5,10,9,8,10,7,11}; for(int i:test) { System.out.print(i+" "); } System.out.println(); selectSort(test); for(int j:test) { System.out.print(j+" "); } } static void selectSort(int unordered[]) { int len = unordered.length; int temp,j; for(int i=0;i<len-1;i++) { j=i; for(int k=i+1;k<len;k++) { if(unordered[k]<unordered[j]) { j=k; //如果有比第一个还小的，则将j指向较小的那个，最后j将指向最小的那个 } } if(i!=j) //j有变动才交换，无变动不交换 { temp=unordered[j]; unordered[j]=unordered[i]; unordered[i]=temp; } } } }二、插入排序
public class InsertSort{ public static void main(String[] args) { InsertSort is = new InsertSort(); int test[]={1,3,2,6,4,5,10,9,8,10,7,11}; for(int i:test) { System.out.print(i+" "); } System.out.println(); is.insertSort(test); for(int j:test) { System.out.print(j+" "); } } /** *插入排序基本思想： *将一组数列看做是一个有序数列和一个无序数列的组合，每次在有序数列中插入一个数，使之仍然为有序数列。 *时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。 *@param unordered 一个无序列表(为简单起见，假设为整型数组)。 */ void insertSort(int unsorted[]) { int len=unsorted.length; int j,temp; for(int i=1;i<len;i++) { if(unsorted[i]<unsorted[i-1]) { temp=unsorted[i]; for(j=i-1;temp<unsorted[j];j--) //将比较条件放在for循环里面，一旦发现有比有序序列小的数，则进行一次插入排序 unsorted[j+1]=unsorted[j]; unsorted[j+1]=temp; } } } }三、冒泡排序
public class BubbleSort{ public static void main(String[] args) { BubbleSort bs = new BubbleSort(); int test[]={1,3,2,6,4,5,10,9,8,10,7,11}; for(int i:test) { System.out.print(i+" "); } System.out.println(); bs.bubbleSort(test); for(int j:test) { System.out.print(j+" "); } } /** *冒泡排序的基本思想： *通过将数组中的相邻数字进行两两比较，将较大的沉底，较小的浮出水面。 *时间复杂度为O(n2),空间复杂度O(1),因为只使用了一个辅助变量，且是在原记录数据上进行操作的。 *@param unsorted[] 一个无序数组，假定为整型数组。 */ void bubbleSort(int unsorted[]) { int len = unsorted.length; int temp; for(int i=0;i<len;i++) { for(int j=i;j<len-1;j++) { if(unsorted[j+1]<unsorted[j]) { temp=unsorted[j]; unsorted[j]=unsorted[j+1]; unsorted[j+1]=temp; } } } } }四、快速排序
public class QuickSort{ public static void main(String[] args) { int arr [] = {20,6,15,9,19,21,13,16,22,15}; QuickSort qs = new QuickSort(); qs.quickSort(arr); for(int i:arr) { System.out.print(i+" "); } } /** *快速排序的基本思想： *通过一趟排序将待排记录分割成两个区域， *其中一个区域中的关键字均比另一个区域中的小(区域内不一定是有序的)； *然后分别对这两个区域进行分割，即递归执行。 *时间复杂度为O(nlogn),最坏的情况下是O(n2).不稳定。 *@param unsorted[] 一个无序数组，假定为整型数组。 */ int partition(int unsorted[],int low,int high) { int temp=unsorted[low]; while(low<high) { while(low<high&&unsorted[high]>=temp) high--; //如果高位大于临时值，则降低高位，直至小于temp,将此值赋予低位； unsorted[low]=unsorted[high]; while(low<high&&unsorted[low]<=temp) low++; //如果低位小于临时值，则增加高位，直至大于temp,将此值赋予高位； unsorted[high]=unsorted[low]; }//while unsorted[low]=temp; //将temp赋予低位 return low; //返回低位数字 } void qSort(int unsorted[],int s,int t) { int temp; if(s<t) { temp=partition(unsorted,s,t); qSort(unsorted,s,temp); //递归调用 qSort(unsorted,temp+1,t); //递归调用 }//if } void quickSort(int unsorted[]) { qSort(unsorted,0,unsorted.length-1); } }五、归并排序
public class MergeSort1 { /** * 归并排序的基本思想 * 将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。 * 然后再把有序子序列合并为整体有序序列 * 时间复杂度为O(nlogn) * 稳定排序方式 * @param nums 待排序数组 * @return 输出有序数组 */ public static int[] sort(int[] nums, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 左边 sort(nums, low, mid); // 右边 sort(nums, mid + 1, high); // 左右归并 merge(nums, low, mid, high); } return nums; } 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]; } } // 归并排序的实现 public static void main(String[] args) { int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 }; MergeSort1.sort(nums, 0, nums.length-1); for(int i : nums) { System.out.print(i+","); } } }