package com.cjs.sort; /** * 此类用来提供针对整数的各种排序算法 * * @author S * @version 1.0 */ public class MySort { /** * 冒泡排序来实现一系列整数的升序排列，改变了传入的数组 * * @param a * 传入的整形数组，对其进行排序的目标数组 * @return void */ public static void bubbleSort(int a[]) { int n = a.length; for (int i = 1; i <= n - 1; i++) { for (int j = 0; j < n - i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } } /** * 选择排序来实现一系列整数的升序排列，改变了传入的数组 * * @param a * 传入的整形数组，对其进行排序的目标数组 * @return void */ public static void selectSort(int[] a){ int n = a.length; for(int i = 0; i < n; i++){ int x = a[i], k = i; for(int j = i+1; j < n; j++){ if(a[j] < x){ x = a[j]; k = j; } } a[k] = a[i]; a[i] = x; } } /** * 插入排序来实现一系列整数的升序排列，改变了传入的数组 * * @param a * 传入的整形数组，对其进行排序的目标数组 * @return void */ public static void insertSort(int[] a){ int n = a.length; for(int i = 1; i < n; i++){ int x = a[i],k = i; for(int j = i-1; j >= 0; j--){ if(a[j] > x){ a[j+1] = a[j]; k = j; } } a[k] = x; } } static int[] temp = new int[100 * 100]; // 归并排序所用到的临时数组 /** * 归并排序来实现一系列整数的升序排列，改变了传入的数组，所排数组的大小不能超过10000 * * @param a * 传入的整形数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ public static void mergeSort(int a[], int left, int right) { // 至少有两个元素，也是递归的结束条件 if (left < right) { int mid = (left + right) / 2; mergeSort(a, left, mid); mergeSort(a, mid + 1, right); // 合并到临时数组temp Merge(a, temp, left, mid, right); // 复制回数组a Copy(a, temp, left, right); } } /** * 归并排序中的合并操作，将二分后的数组按升序排列 * * @param a * 传入的数组 * @param t * 要合并到的临时数组 * @param left * 传入数组的左边界下标 * @param mid * 传入数组的中间下标 * @param right * 传入数组的右边界下标 * @return void */ private static void Merge(int a[], int t[], int left, int mid, int right) { // 合并c[1:m]和c[m+1:r]到d[l,r] int i = left, j = mid + 1, k = left; // 两表中元素比较，类似于打擂台，大的复制到临时数组中 while (i <= mid && j <= right) { if (a[i] < a[j]) { t[k++] = a[i++]; } else { t[k++] = a[j++]; } } // 若前一个子序列剩余，则直接复制入临时数组 if (i > mid) { for (int q = j; q <= right; q++) t[k++] = a[q]; } // 后一个子序列 else { for (int q = i; q <= mid; q++) t[k++] = a[q]; } } /** * 归并排序中的复制操作，将数据从临时数组中复制到传入的原数组 * * @param a * 传入的数组 * @param t * 保存数据的临时数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ private static void Copy(int a[], int t[], int left, int right) { for (int i = left; i <= right; i++) a[i] = t[i]; } /** * 快速排序来实现一系列整数的升序排列，改变了传入的数组 * * @param a * 传入的整形数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ public static void quickSort(int a[], int left, int right) { if (left < right) { int x = Partition(a, left, right); quickSort(a, left, x - 1); quickSort(a, x + 1, right); } } /** * 快速排序中用来对元素进行划分，基准元素为a[left] * * @param a * 传入的整形数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return i 划分后基准元素所处位置的下标 */ private static int Partition(int[] a, int left, int right) { int x = a[left]; int i = left, j = right; while (i < j) { while (i < j && a[j] >= x) j--; if (i < j) { a[i] = a[j]; i++; } while (i < j && a[i] < x) i++; if (i < j) { a[j] = a[i]; j--; } } a[i] = x; return i; } }
泛型实现：
package com.cjs.alogrithm; /** * 此类采用泛型方法来提供对各种类型数据的各种排序算法 * * @author S * @version 1.0 */ public class MySort { /** * 冒泡排序来实现一系列数据的升序排列，改变了传入的数组 * * @param a * 传入的存储数据的数组，对其进行排序的目标数组 * @return void */ public static <T extends Comparable<T>> void bubbleSort(T a[]) { int n = a.length; for (int i = 1; i <= n - 1; i++) { for (int j = 0; j < n - i; j++) { if ((a[j]).compareTo(a[j + 1]) > 0) { T t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } } /** * 选择排序来实现一系列数据的升序排列，改变了传入的数组 * * @param a * 传入的存储数据数组，对其进行排序的目标数组 * @return void */ public static <T extends Comparable<T>> void selectSort(T[] a) { int n = a.length; for (int i = 0; i < n; i++) { T x = a[i]; int k = i; for (int j = i + 1; j < n; j++) { if (a[j].compareTo(x) < 0) { x = a[j]; k = j; } } a[k] = a[i]; a[i] = x; } } /** * 插入排序来实现一系列数据的升序排列，改变了传入的数组 * * @param a * 传入的存储数据的数组，对其进行排序的目标数组 * @return void */ public static <T extends Comparable<T>> void insertSort(T[] a) { int n = a.length; for (int i = 1; i < n; i++) { T x = a[i]; int k = i; for (int j = i - 1; j >= 0; j--) { if (a[j].compareTo(x) > 0) { a[j + 1] = a[j]; k = j; } } a[k] = x; } } /** * 归并排序来实现一系列数据的升序排列，改变了传入的数组，需要额外提供一个临时数组来辅助排序 * * @param a * 传入的存储数据的数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ public static <T extends Comparable<T>> void mergeSort(T a[], T temp[], int left, int right) { // 至少有两个元素，也是递归的结束条件 if (left < right) { int mid = (left + right) / 2; mergeSort(a, temp, left, mid); mergeSort(a, temp, mid + 1, right); // 合并到临时数组temp Merge(a, temp, left, mid, right); // 复制回数组a Copy(a, temp, left, right); } } /** * 归并排序中的合并操作，将二分后的数组按升序排列 * * @param a * 传入的数组 * @param t * 要合并到的临时数组 * @param left * 传入数组的左边界下标 * @param mid * 传入数组的中间下标 * @param right * 传入数组的右边界下标 * @return void */ private static <T extends Comparable<T>> void Merge(T a[], T t[], int left, int mid, int right) { // 合并c[1:m]和c[m+1:r]到d[l,r] int i = left, j = mid + 1, k = left; // 两表中元素比较，类似于打擂台，大的复制到临时数组中 while (i <= mid && j <= right) { if (a[i].compareTo(a[j]) < 0) { t[k++] = a[i++]; } else { t[k++] = a[j++]; } } // 若前一个子序列剩余，则直接复制入临时数组 if (i > mid) { for (int q = j; q <= right; q++) t[k++] = a[q]; } // 后一个子序列 else { for (int q = i; q <= mid; q++) t[k++] = a[q]; } } /** * 归并排序中的复制操作，将数据从临时数组中复制到传入的原数组 * * @param a * 传入的数组 * @param t * 保存数据的临时数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ private static <T extends Comparable<T>> void Copy(T a[], T t[], int left, int right) { for (int i = left; i <= right; i++) a[i] = t[i]; } /** * 快速排序来实现一系列数据的升序排列，改变了传入的数组 * * @param a * 传入的存储数据的数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return void */ public static <T extends Comparable<T>> void quickSort(T a[], int left, int right) { if (left < right) { int x = Partition(a, left, right); quickSort(a, left, x - 1); quickSort(a, x + 1, right); } } /** * 快速排序中用来对元素进行划分，基准元素为a[left] * * @param a * 传入的存储数据的数组，对其进行排序的目标数组 * @param left * 传入数组的左边界下标 * @param right * 传入数组的右边界下标 * @return i 划分后基准元素所处位置的下标 */ private static <T extends Comparable<T>> int Partition(T[] a, int left, int right) { T x = a[left]; int i = left, j = right; while (i < j) { while (i < j && a[j].compareTo(x) >= 0) j--; if (i < j) { a[i] = a[j]; i++; } while (i < j && a[i].compareTo(x) < 0) i++; if (i < j) { a[j] = a[i]; j--; } } a[i] = x; return i; } }