最全排序算法原理解析、java代码实现以及总结归纳

public class SortMethod { public static void main(String[] args) { int[] array = {1, 34, 45, 13, 6, 68, 47, 22, 49, 33, 7, 16, 50};
// int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
// int[] array = {13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; System.out.println("排序前数组为：");
printArray(array);
System.out.println("----------------------------------交 换 排 序----------------------------------");
bubbleSort(array.clone());
shellSortUsingBubble(array.clone());
quickSort(array.clone());
System.out.println("----------------------------------插 入 排 序----------------------------------");
insertionSort(array.clone());
shellSort(array.clone());
System.out.println("----------------------------------选 择 排 序----------------------------------");
selectionSort(array.clone());
heapSort(array.clone(), array.length - 1, 0);
System.out.println("----------------------------------归 并 排 序----------------------------------");
mergeSort(array.clone());
System.out.println("----------------------------------计 数 排 序----------------------------------");
countingSort(array.clone(),100);
System.out.println("----------------------------------基 数 排 序----------------------------------");
radixSort(array.clone());
System.out.println("------------------------------------桶 排 序----------------------------------");
bucketSort(array.clone());
System.out.println("------------------------------------------------------------------------------"); } private static void bubbleSort(int[] arr) {
long current = System.currentTimeMillis();
int count = 0, len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
int temp = arr[j + 1]; // 元素交换
arr[j + 1] = arr[j];
arr[j] = temp;
count++;
}
}
}
long cost = System.currentTimeMillis() - current; // System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("bubbleSort 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。");
} /**
* 使用分治法来把一个串（list）分为两个子串（sub-lists）,通过一趟排序将待排记录分隔成独立的两部分
* 其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
*
* @param arr
*/
private static void quickSort(int[] arr) {
long current = System.currentTimeMillis();
// 使用单链表进行排序
int count = spilt(arr.clone(), 0, arr.length - 1, 0);
long cost = System.currentTimeMillis() - current; // System.out.println("使用单链表进行排序花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("quickSort(使用单链表进行排序) 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。"); // current = System.currentTimeMillis();
// // 使用双链表进行排序
count = partition(arr.clone(), 0, arr.length - 1, 0);
// cost = System.currentTimeMillis() - current;
// System.out.println("使用双链表进行排序花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("quickSort(使用双链表进行排序) 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。");
} private static int spilt(int[] arr, int low, int high, int count) {
if (low >= high) {
return count; //未发生比较，比较计数器不变
}
int len = arr.length;
int temp, i = low;
for (int j = low + 1; j < len; j++) {
if (arr[low] > arr[j]) {
temp = arr[j];
arr[j] = arr[i + 1];
arr[i + 1] = temp;
i++;
count++;
}
}
if (i > low) {
temp = arr[i];
arr[i] = arr[low];
arr[low] = temp;
count++;
}
count = spilt(arr, low, i - 1, count);
count = spilt(arr, i + 1, high, count);
return count;
} public static int partition(int a[], int low, int high, int count) {
if (low < high) {
//划分数组并获取比较元素的位置
int x = a[low], temp; //将该数组第一个元素设置为比较元素
int i = low;
int j = high;
while (i < j) {
while (i < j && a[j] >= x)
j--; //从右至左找到第一个小于比较元素的数
while (i < j && a[i] <= x)
i++; //从左至右找到第一个大于比较元素的数
/*需要注意的是，这里的j--与i++的顺序不可以调换！
*如果调换了顺序，i会走过头，以至于将后面较大的元素交换到数组开头*/ //将大数与小数交换
if (i != j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
count++;
} }
//将比较元素交换到期望位置
temp = a[i];
a[i] = a[low];
a[low] = temp;
count++;
count = partition(a, low, i - 1, count); //对比较元素左边进行排序
count = partition(a, i + 1, high, count); //对比较元素右边进行排序
}
return count;
} // private static int partition(int[] arr, int low, int high, int count) {
// if (low >= high) {
// return count; //未发生比较，比较计数器不变
// }
//
// int temp;
// int i = low + 1, j = high;
// if (high == low + 1 && arr[high] < arr[low]) {
// temp = arr[low];
// arr[low] = arr[high];
// arr[high] = temp;
// count++;
// return count;
// }
// while (i < j) {
// while (arr[i] <= arr[low] && j > i) {
// i++;
// }
// while (arr[j] >= arr[low] && j > i) {
// j--;
// }
// if (i < j) {
// temp = arr[j];
// arr[j] = arr[i];
// arr[i] = temp;
// count++;
// }
// }
// if (i > low + 1) {
// temp = arr[i - 1];
// arr[i - 1] = arr[low];
// arr[low] = temp;
// count++;
// }
// count = partition(arr, low, i - 2, count);
// count = partition(arr, i, high, count);
// return count;
// } /**
* 插入排序
*
* @param arr
*/
private static void insertionSort(int[] arr) {
long current = System.currentTimeMillis();
int len = arr.length;
int preIndex, temp, count = 0;
for (int i = 1; i < len; i++) {
preIndex = i - 1;
temp = arr[i];
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + 1] = arr[preIndex];
count++;
preIndex--;
}
arr[preIndex + 1] = temp;
count++;
}
long cost = System.currentTimeMillis() - current; // System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("insertionSort 发生了 " + count + " 次移动。");
} /**
* shell Sort using exchange method(希尔排序内部用了交换的方式)
*
* @param arr
*/
private static void shellSortUsingBubble(int[] arr) {
long current = System.currentTimeMillis();
int count = 0, len = arr.length;
//间隔变化
for (int gap = len / 2; gap > 0; gap /= 2) {
//对固定间隔的排序
for (int i = gap; i < len; i++) {
for (int j = i; j > gap - 1; j -= gap) {
if (arr[j] < arr[j - gap]) {
int temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
count++;
}
}
}
}
long cost = System.currentTimeMillis() - current; // System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("shellSortUsingBubble 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。");
} /**
* shell Sort using insert Method: Knuth序列
* h = 1
* h = 3*h + 1
* 一个很长的数组，我们要用能对这个数组采用最大的间隔。最大间隔不能超过数组长度的1/3，当h>1/3时 3h+1 就大于整个数组的长度了，所以就不适合了。
*/
public static void shellSort(int[] arr) {
long current = System.currentTimeMillis();
int temp, h = 1, count = 0;
while (h < arr.length / 3) {
h = h * 3 + 1;
} for (int gap = h; gap > 0; gap = (gap - 1) / 3) { for (int i = gap; i < arr.length; i++) {
temp = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + gap] = arr[preIndex];
count++;
preIndex -= gap;
}
arr[preIndex + gap] = temp;
count++;
}
}
long cost = System.currentTimeMillis() - current; // System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("shellSort 发生了 " + count + " 次移动。");
} private static void selectionSort(int[] arr) {
long current = System.currentTimeMillis();
int len = arr.length;
int minIndex, temp, count = 0;
for (int i = 0; i < len - 1; i++) {
minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
count++;
}
long cost = System.currentTimeMillis() - current; // System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("selectionSort 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。");
} private static int heapSort(int[] arr, int heapSize, int count) {
int temp;
if (heapSize > 0) {
for (int i = heapSize; i > 0; i--) {
if (arr[(i - 1) / 2] < arr[i]) {
temp = arr[i];
arr[i] = arr[(i - 1) / 2];
arr[(i - 1) / 2] = temp;
count++;
}
}
temp = arr[0];
arr[0] = arr[heapSize];
arr[heapSize] = temp;
count++;
count = heapSort(arr, --heapSize, count);
} else {
// System.out.println("排序后结果为：");
// printArray(arr);
System.out.println("selectionSort 发生了 " + count + " 次交换, 相当于 " + count * 3 + " 次移动。");
}
return count;
} private static void mergeSort(int[] arr) {
long current = System.currentTimeMillis();
int[] temp = new int[arr.length];
divide(0, arr.length - 1, arr, temp);
long cost = System.currentTimeMillis() - current;
System.out.println("当前排序算法花费时间为：" + cost + " ms。");
} private static void divide(int low, int high, int[] arr, int[] temp) {
if (high <= low) {
return;
}
int mid = (low + high) / 2;
divide(low, mid, arr, temp);
divide(mid + 1, high, arr, temp); for (int i = low; i <= high; i++) {
temp[i] = arr[i];
} int i = low, j = mid + 1;
for (int index = low; index <= high; ++index) {
// 如果低位数组用完 则 将高位数组依次复制
if (i > mid) {
arr[index] = temp[j++];
}
// 如果高位数组用完 则 将低位数组依次复制
else if (j > high) {
arr[index] = temp[i++];
}
// 如果高位数组最左侧元素 小于 低位数组最左侧元素 则 将高位数组最左侧元素复制
else if (temp[j] < temp[i]) {
arr[index] = temp[j++];
}
// 如果低位数组最左侧元素 小于或等于 高位数组最左侧元素 则 将低位数组最左侧元素复制
else {
arr[index] = temp[i++];
}
} if (low == 0 && high == arr.length - 1) {
System.out.println("排序后结果为：");
printArray(arr);
}
} private static void countingSort(int[] arr,int range) {
long current = System.currentTimeMillis(); //假设数值范围为0-100
int[] count = new int[range+1];
int len = arr.length;
for (int i = 0; i < len; i++) {
count[arr[i]]++;
}
int countLen = count.length;
int data = 0;
for (int j = 0; j < countLen; j++) {
for (int k = 0; k < count[j]; k++) {
arr[data++] = j;
}
} long cost = System.currentTimeMillis() - current;
// System.out.println("当前排序算法花费时间为：" + cost + " ms。");
// System.out.println("排序后结果为：");
printArray(arr); } /**
* 高位优先法
*
* @param arr 待排序列，必须为自然数
*/
private static void radixSort(int[] arr) {
long current = System.currentTimeMillis();
//待排序列最大值
int max = arr[0];
int exp;//指数 //计算最大值
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
} //从个位开始，对数组进行排序
for (exp = 1; max / exp > 0; exp *= 10) {
//存储待排元素的临时数组
int[] temp = new int[arr.length];
//分桶个数
int[] buckets = new int[10]; //将数据出现的次数存储在buckets中
for (int value : arr) {
//(value / exp) % 10 :value的最底位(个位)
buckets[(value / exp) % 10]++;
} //更改buckets[i]，
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
} //将数据存储到临时数组temp中
for (int i = arr.length - 1; i >= 0; i--) {
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
} //将有序元素temp赋给arr
System.arraycopy(temp, 0, arr, 0, arr.length);
} long cost = System.currentTimeMillis() - current;
System.out.println("当前排序算法花费时间为：" + cost + " ms。");
System.out.println("排序后结果为：");
printArray(arr); } public static void bucketSort(int[] arr) {
long current = System.currentTimeMillis();
if (arr == null || arr.length == 0) {
return;
}
int len = arr.length;
// 根据原始序列的长度，设置桶的数量。这里假设每个桶放平均放4个元素
int bucketCount = len / 4;
// 遍历原始序列，找出最大值和最小值
int min = 0, max = 0;
for (int i = 0; i < len; i++) {
if (arr[i] > max) {
max = arr[i];
} else if (arr[i] < min) {
min = arr[i];
}
}
// 每个桶的数值范围
int range = (max - min + 1) / bucketCount;
int[][] buckets = new int[bucketCount][];
// 遍历原始序列
for (int i = 0; i < len; i++) {
int val = arr[i];
// 计算当前值属于哪个桶
int bucketIndex = (int) Math.floor((val - min) / range);
// 向桶中添加元素
buckets[bucketIndex] = appendItem(buckets[bucketIndex], val);
}
// 最后合并所有的桶
int k = 0;
for (int[] b : buckets) {
if (b != null) {
for (int i = 0; i < b.length; i++) {
arr[k++] = b[i];
}
}
}
long cost = System.currentTimeMillis() - current;
System.out.println("当前排序算法花费时间为：" + cost + " ms。");
System.out.println("排序后结果为：");
printArray(arr);
} private static int[] appendItem(int[] bucketArr, int val) {
if (bucketArr == null || bucketArr.length == 0) {
return new int[]{val};
}
// 拷贝一下原来桶的序列，并增加一位
int[] arr = Arrays.copyOf(bucketArr, bucketArr.length + 1);
// 这里使用插入排序，将新的值val插入到序列中
int i;
for (i = arr.length - 2; i >= 0 && arr[i] > val; i--) {
// 从新序列arr的倒数第二位开始向前遍历（倒数第一位是新增加的空位，还没有值）
// 如果当前序列值大于val，那么向后移位
arr[i + 1] = arr[i];
}
arr[i + 1] = val;
return arr;
} private static void printArray(int[] arr) {
System.out.print("\t");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} }