时间复杂度：快些以O(nlogn)的速度归队
稳定性：心情不稳定，快些选一堆好朋友来聊天吧
若文件初始有序，则最好选用直接插入排序或者冒泡排序
- 冒泡排序：
两个for循环，平均时间复杂度：O（n^2）、稳定
public static void BubbleSort(int[] a) {
if (a == null || a.length == 0)
return;
for (int i = a.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
- 快速排序:
可使用递归方式或非递归方式 o(nlogn) 不稳定
public static void main(String[] args) {
int a[] = { 6, 2, 3, 5, 1, 6, 0 };
QuickSort(a, 0, a.length-1);
for (int i : a) {
System.out.print(i + " ");
}
}
//求枢轴点，一次排序后，枢轴点左侧都小于枢轴元素，右侧都大于枢轴元素
public static int Partition(int a[], int low, int high) {
int pivot = a[low];// 以low的元素为枢轴元素
while (low < high) {// 跳出条件
while (low < high && a[high] >= pivot)
--high; //若high处的元素大于枢轴元素，则high往前移一位
a[low] = a[high];//将比枢轴小的元素移到左边
while(low < high && a[low] <= pivot) ++low;
a[high] = a[low];
}
a[low] = pivot;//枢轴元素放到最终位置
return low;
}
//递归方式：
public static void QuickSort(int a[], int low, int high){
if(low<high){
int pivot = Partition(a, low, high);
QuickSort(a, low, pivot-1);
QuickSort(a, pivot+1, high);
}
}
//非递归方式
public static void QuickSort(int a[], int low, int high) {
Stack<Integer> st = new Stack<>();
if (low < high) { //如果low、high符合条件，将low和high入栈
st.push(high);
st.push(low);
}
while (!st.isEmpty()) {
int l = st.pop();
int h = st.pop();
int pivot = Partition(a, l, h);//求枢轴点
//将符合条件的区间对入栈
if (l < pivot) {
st.push(pivot - 1);
st.push(l);
}
if (h > pivot) {
st.push(h);
st.push(pivot + 1);
}
}
}
*堆排序：
按照[n/2]~1的顺序筛选,O(nlogn)
//堆排序
public static void HeapSort(int a[], int len) {
BuildMaxHeap(a, len);//构建堆
for (int i = len-1; i >= 1; i--) {
//将堆顶元素放在最后一个位置，堆顶元素最大，将其输出，
//然后将剩余的元素再次进行堆排序，即可按照从大到小的顺序输出元素。
//堆中元素从a[1]开始，a[0]为暂存位
int temp = a[i];
a[i] = a[1];
a[1] = temp;
System.out.println(a[i]);
Adjust(a, 1, i - 1);
}
}
//构建堆
public static void BuildMaxHeap(int a[], int len) {
for (int i = len / 2; i > 0; i--) {
// 从【2/n】~1进行排序
Adjust(a, i, len);
}
}
public static void Adjust(int a[], int k, int len) {
a[0] = a[k];// a[0]用来暂存，实质的值在a[1-len]
for (int i = k * 2; i <= len; i *= 2) {
if (i + 1 < len && a[i] < a[i + 1])
i++;// 找到最大的孩子
if (a[0] >= a[i])
break;
else {
a[k] = a[i];
k = i;
}
}
a[k] = a[0];
}
