八大排序代码——总结

代码——总结"/>

八大排序代码——总结

稳定排序有：插入排序、冒泡排序、归并排序、基数排序
（基冒插归）
不稳定排序有：选择排序、快速排序、希尔排序、堆排序
（快选希堆）

默认从小到大排序

插入排序 O(n^2) 稳定

void insertSort(int a[], int n)
{for(int i = 1; i < n; i ++){int tmp = a[i],j;for(j = i; j > 0 && tmp < a[j-1]; j--)a[j] = a[j-1];a[j] = tmp;}
}

冒泡排序 O(n^2) 稳定

void bubbleSort(int a[], int n)
{for(int i = n-1; i > 0; i --){for(int j = 0; j < i; j ++){if(a[j] > a[j+1]) swap(a[j],a[j+1]);}}
}

冒泡排序优化版 O(n^2) 稳定

void bubbleSort(int a[], int n)
{for(int i = n-1; i > 0; i --){bool flag = true;for(int j = 0; j < i; j ++){if(a[j] > a[j+1]) swap(a[j],a[j+1]),flag = false;}if(flag) break;}
}

归并排序 O(nlogn) 稳定

int n;
int q[N],tmp[N];void merge_sort(int q[],int l,int r){if(l >= r) return ;int mid = (l+r)/2;merge_sort(q,l,mid);merge_sort(q,mid+1,r);int i = l,j = mid+1,k = 0;while(i <= mid && j <= r){if(q[i] < q[j]) tmp[k++] = q[i++];else tmp[k++] = q[j++];}while(i <= mid) tmp[k++] = q[i++];while(j <= r) tmp[k++] = q[j++];for(int i = l,j = 0; i <= r; i ++,j ++) q[i] = tmp[j];
}

选择排序 O(n^2)

void selectSort(int a[], int n)
{for(int i = 0; i < n - 1; i++){for(int j = i + 1; j < n; j++){if(a[i] > a[j]) swap(a[i], a[j]);}}
}

快速排序 O(nlogn)

//教科书版：取左边界为基值
void quick_sort(int l,int r){if(l>= r) return ;int i = l, j = r,tmp = q[l];while(i < j){while(i < j && q[j] >= tmp) j--;if(i < j) q[i++] = q[j];while(i < j && q[i] <= tmp) i++;if(i < j) q[j--] = q[i];}q[i] = tmp;quick_sort(l,i-1);quick_sort(i+1,r);
}

//y总写的快排
void quick_sort(int l,int r){if(l >= r) return ;int x = q[l+r>>1];int i = l - 1,j = r + 1;while(i < j){do i ++; while(q[i] < x);do j --; while(q[j] > x);if(i < j) swap(q[i],q[j]);}quick_sort(l,j);quick_sort(j+1,r);
}

堆排序 O(nlogn)

int heap[N];void down(int u){int t = u;if(2*u <= n && heap[2*u] < heap[t]) t = 2*u;if(2*u + 1 <= n && heap[2*u+1] < heap[t]) t = 2*u+1;if(t != u){swap(heap[t],heap[u]);down(t);}
}//输出最小的m个数
int main(){cin >> n >> m;for(int i = 1; i <= n; i ++ ) cin >> heap[i];for(int i = n/2; i >= 1; i --) down(i);while(m --){cout<<heap[1]<<' ';heap[1] = heap[n--];down(1);}return 0;
}