我的开源
排序算法
- 冒泡排序
是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
public static void main(String[] args) {
int[] arrays = {5, 1, 4, 3, 2};
int temp;
int isChange;
for (int i = 0; i < arrays.length - 1; i++) {
isChange = 0;
for (int j = 0; j < arrays.length - i - 1; j++) {
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
isChange = 1;
}
}
if (isChange == 0) {
break;
}
}
System.out.println(Arrays.toString(arrays));
}
- 选择排序
是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。
public static void main(String[] args) {
int[] arrays = {5, 1, 4, 3, 2};
int pos ;
int temp;
for (int i = 0; i < arrays.length - 1; i++) {
pos = 0;
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) {
pos = j;
}
}
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i];
arrays[arrays.length - 1 - i] = temp;
}
System.out.println(Arrays.toString(arrays));
}
- 插入排序
基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据
public static void main(String[] args) {
int[] arrays = {5, 1, 4, 3, 2};
int temp;
for (int i = 1; i < arrays.length; i++) {
temp = arrays[i];
int j = i - 1;
while (j >= 0 && arrays[j] > temp) {
arrays[j + 1] = arrays[j];
j--;
}
arrays[j + 1] = temp;
}
System.out.println(Arrays.toString(arrays));
}
- 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
public static void main(String[] args) {
int[] arrays = {5, 1, 4, 3, 2};
quickSort(arrays, 0, 4);
System.out.println(Arrays.toString(arrays));
}
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
int pivot = arr[(L + R) / 2];
while (i <= j) {
while (pivot > arr[i]){
i++;
}
while (pivot < arr[j]){
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (L < j){
quickSort(arr, L, j);
}
if (i < R){
quickSort(arr, i, R);
}
}
- 归并排序
是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
public static void main(String[] args) {
int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
mergeSort(arrays, 0, arrays.length - 1);
System.out.println(Arrays.toString(arrays));
}
/**
* 归并排序
*
* @param arrays
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一个元素，那就不用排序了
if (L == R) {
return;
} else {
//取中间的数，进行拆分
int M = (L + R) / 2;
//左边的数不断进行拆分
mergeSort(arrays, L, M);
//右边的数不断进行拆分
mergeSort(arrays, M + 1, R);
//合并
merge(arrays, L, M + 1, R);
}
}
/**
* 合并数组
*
* @param arrays
* @param L 指向数组第一个元素
* @param M 指向数组分隔的元素
* @param R 指向数组最后的元素
*/
public static void merge(int[] arrays, int L, int M, int R) {
//左边的数组的大小
int[] leftArray = new int[M - L];
//右边的数组大小
int[] rightArray = new int[R - M + 1];
//往这两个数组填充数据
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i];
}
for (int i = M; i <= R; i++) {
rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays数组的第一个元素
int k = L;
//比较这两个数组的值，哪个小，就往数组上放
while (i < leftArray.length && j < rightArray.length) {
//谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个
if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j];
j++;
k++;
}
}
//如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)
while (i < leftArray.length) {
arrays[k] = leftArray[i];
i++;
k++;
}
//如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)
while (j < rightArray.length) {
arrays[k] = rightArray[j];
k++;
j++;
}
}
- 希尔排序
是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
public static void main(String[] args) {
int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
shellSort(arrays);
System.out.println(Arrays.toString(arrays));
}
public static void shellSort(int[] arrays) {
//增量每次都/2
for (int step = arrays.length / 2; step > 0; step /= 2) {
//从增量那组开始进行插入排序，直至完毕
for (int i = step; i < arrays.length; i++) {
int j = i;
int temp = arrays[j];
// j - step 就是代表与它同组隔壁的元素
while (j - step >= 0 && arrays[j - step] > temp) {
arrays[j] = arrays[j - step];
j = j - step;
}
arrays[j] = temp;
}
}
}
- 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
public static void main(String[] args) {
int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
// 完成一次建堆..
maxHeapify(arrays, arrays.length - 1);
int size = arrays.length - 1;
for (int i = 0; i < arrays.length; i++) {
//交换
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
// 调整位置
heapify(arrays, 0, size);
size--;
}
System.out.println( Arrays.toString(arrays));
}
/**
* 完成一次建堆，最大值在堆的顶部(根节点)
*/
public static void maxHeapify(int[] arrays, int size) {
// 从数组的尾部开始，直到第一个元素(角标为0)
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
/**
* 建堆
* @param arrays 看作是完全二叉树
* @param currentRootNode 当前父节点位置
* @param size 节点总数
*/
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子树和右字数的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把当前父节点位置看成是最大的
int max = currentRootNode;
if (left < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[right]) {
max = right;
}
}
//如果最大的不是根元素位置，那么就交换
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//继续比较，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
- 基数排序
基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
public static void main(String[] args) {
int[] arrays = {1, 2, 4, 7, 3, 2, 9, 5, 2, 1, 8};
radixSort(arrays);
System.out.println(Arrays.toString(arrays));
}
/**
* 递归，找出数组最大的值
*
* @param arrays 数组
* @param L 左边界，第一个数
* @param R 右边界，数组的长度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果该数组只有一个数，那么最大的就是该数组第一个值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整体的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//桶
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}