八大排序(Java实现)
- 冒泡排序
算法描述：冒泡排序是一种交换排序，主要思想就是比较相邻元素，然后将较小的元素交换到前面，较大的元素交换到后面。
时间复杂度：O(N^2)
稳定性描述：由于交换是逐个进行的，且相等的元素不进行交换，所以冒泡法排序是一种稳定排序算法。
public class BubbleSort {
public static void bubbleSort(int[] n){
for(int i = 0;i<n.length;i++){
for(int j = 0;j<n.length-i-1;j++){
if(n[j]>n[j+1]){
n[j]^=n[j+1];
n[j+1]^=n[j];
n[j]^=n[j+1];
}
}
}
}
}
- 直接选择排序
算法描述：直接选择排序是一种选择排序，主要思想是在给定序列中选择最小的元素，与序列中第1个元素进行交换，然后在余下的元素中选择总序列中第2小的，与序列中第2个元素进行交换，以此类推，不断选择出第i小的元素与总序列第i位元素交换，直到选到最后一个最大元素。
时间复杂度：O(N^2)
稳定性描述：这种选择的方法会导致稳定性的问题，例如：序列{4,4,2}，在第一次选择交换后序列变为{2,4,4}，原序列中第一个4就移动到了原序列中第二个4的后面，所以直接选择排序是一种不稳定排序算法。
public class SelectSort {
public static void SelectSort(int[] n) {
for (int i = 0; i < n.length; i++) {
int min = n[i];
int index = i;
for (int j = i + 1; j < n.length; j++) {
if (n[j] < min) {
min = n[j];
index = j;
}
}
int temp = n[i];
n[i] = n[index];
n[index] = temp;
}
}
}
- 直接插入排序
算法描述：直接插入排序是一种插入排序，主要思想是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果不比它小则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
时间复杂度：O(N^2)
稳定性描述：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以直接插入排序是一种稳定的排序算法。
public class InsertSort {
public static void insertSort(int[] n) {
for (int i = 0; i < n.length; i++) {
int j, index = 0;
for (j = i - 1; j >= 0; j--) { //找到要插入的位置，记做index
if (n[i] >= n[j]) {
index = j + 1;
break;
}
index = j;
}
for (j = i; j > index; j--) { //插入并移动元素
n[j] ^= n[j - 1];
n[j - 1] ^= n[j];
n[j] ^= n[j - 1];
}
}
}
}
-
希尔排序
-
快速排序
算法描述：快速排序是一种交换排序，可以看做是冒泡排序的升级版。快速排序会选择一个标兵（一般选择当前子序列的第一个元素或者最后一个元素），然后将小于标兵的元素放置在标兵左边、大于标兵的元素放置在标兵的右边，这样就生成了另外两个子序列，然后进行同样地操作至子序列不可分为止。
时间复杂度为：O(N*log(N))
稳定性描述：因为快速排序在进行交换时会将前面已经经过交换的元素进行打乱，所以这是一个不稳定排序算法。
代码实现：
public class QickSort {
public static void IQickSort(int[] n, int left, int right) {
int dp;//标兵在全序列的位置，即子序列分割点
if (left < right) {
dp = partition(n, left, right);
IQickSort(n, left, dp - 1);//左边子序列递归快排
IQickSort(n, dp + 1, right);//右边子序列递归快排
}
}
private static int partition(int[] n, int left, int right) {
int pivot = n[left];//标兵
while (left < right) {
while (left < right && n[right] >= pivot) {
right--;
}//找出标兵右边比标兵小的元素
if (left < right)
n[left++] = n[right];//交换
while (left < right && n[left] <= pivot) {
left++;
}//找出标兵左边比标兵大的元素
if (left < right)
n[right--] = n[left];//交换
}
n[left] = pivot;
return left;//返回标兵最终的位置
}
}
- 堆排序
算法描述：堆排序是一种选择排序，可以看做是直接选择排序的升级版，堆排序是以大顶堆（小顶堆也能实现，这里以大顶堆来进行说明）的性质保持为基础进行选择排序，堆的节点是节点i的孩子（即节点2*i和2*i+1），大顶堆要求父节点大于或等于两个节点。为了维持这个性质，对于一个以i为根的子树A，从元素A[i],A[left(i)],A[right(i)]中选出最大值，如果最大值是根节点则结束，如果是左(右)节点则与根节点进行交换，并对左(右)子树继续进行选择交换，对一个序列构造大顶堆时从第n/2个元素向前进行性质维持就能构造出一个大顶堆。堆排序的思想是选出当前大顶堆的根节点，将其与最后的节点元素进行交换，再移除最后的节点，然后维持大顶堆的性质进行选择交换，直到所有元素移除即完成排序工作。
时间复杂度为：O(N*Log(N))
稳定性描述：堆排序的过程是从第n/2开始和其子节点共3个值选择大顶堆，这3个元素之间的选择当然不会破坏稳定性。但当为(n/2)-1，(n/2)-2 ... 这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第(n/2)-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
public class HeapSort {
/*交换两个数值*/
public static void swap(int[] n, int index1, int index2) {
n[index1] ^= n[index2];
n[index2] ^= n[index1];
n[index1] ^= n[index2];
}
public static void IHeapSort(int[] n, int len) {
buildMaxHeapify(n, len);
for (int i = len - 1; i >= 1; i--) {
swap(n, 0, i);
maxHeapify(n, 0, i);
}
}
/*建立大顶堆*/
public static void buildMaxHeapify(int[] n, int len) {
//从第一个非叶子节点开始大顶堆化
for (int i = len / 2 - 1; i >= 0; i--) {
maxHeapify(n, i, len);
}
}
/*将树中数值最大的节点交换到根节点*/
public static void maxHeapify(int[] n, int i, int heapSize) {
int left = (i + 1) * 2 - 1;//左叶子节点
int right = (i + 1) * 2;//右叶子节点
int largest = i;
if (left < heapSize && n[left] > n[largest]) {
largest = left;
}
if (right < heapSize && n[right] > n[largest]) {
largest = right;
}
if (largest != i) {
swap(n,i,largest);
maxHeapify(n, largest, heapSize);
}
}
}
- 归并排序
算法描述：归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，合并时采用相互比较两边序列最小值先放入合并序列的方法，然后按顺序不断比较放入合并序列。不断合并直到原序列全部排好序。
时间复杂度：O(N*Log(N))
稳定性描述：可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序是稳定的排序算法。
public class MergeSort {
/*用递归的方法将数组拆分*/
public static void mergeSort(int[] n, int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
mergeSort(n, left, mid);
mergeSort(n, mid + 1, right);
merge(n, left, right, mid);
}
}
/*归并的具体实现*/
public static void merge(int[] n, int left, int right, int mid) {
int[] temp = new int[right - left + 1];
int indexL = left;
int indexR = mid + 1;
int index = 0;
//将较小的元素插入到temp数组中
while (indexL <= mid && indexR <= right) {
if (n[indexL] < n[indexR]) {
temp[index++] = n[indexL++];
} else {
temp[index++] = n[indexR++];
}
}
//将还没有插入的元素插入到temp数组中
while (indexL <= mid)
temp[index++] = n[indexL++];
while (indexR <= right)
temp[index++] = n[indexR++];
//将归并后的数组覆盖到原数组中
for (int i = 0; i < temp.length; i++) {
n[i + left] = temp[i];
}
}
}
- 基数排序