package main
import "fmt"
// 归并排序
func mergeSort(nums []int) []int {
numsLen := len(nums)
if numsLen < 2 {
return nums
}
middleIndex := numsLen / 2
left := nums[: middleIndex]
right := nums[middleIndex:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1: ]
} else {
result = append(result, right[0])
right = right[1: ]
}
}
if len(left) != 0 {
result = append(result, left...)
}
if len(right) != 0 {
result = append(result, right...)
}
return result
}
func main(){
var n int
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
var tmp int
fmt.Scan(&tmp)
nums[i] = tmp
}
res := mergeSort(nums)
for _, num := range res {
fmt.Print(num, " ")
}
} package main
import "fmt"
// 快速排序
func quickSort(nums []int)[]int{
return _quickSort(nums, 0, len(nums) - 1)
}
func _quickSort(nums []int, left, right int) []int {
if left < right {
partitionIndex := partition(nums, left, right)
_quickSort(nums, left, partitionIndex-1)
_quickSort(nums, partitionIndex+1, right)
}
return nums
}
func partition(nums []int, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if nums[pivot] > nums[i] {
nums[i], nums[index] = nums[index], nums[i]
index++
}
}
nums[pivot], nums[index - 1] = nums[index - 1], nums[pivot]
return index - 1
}
func main(){
var n int
fmt.Scan(&n)
nums := make([]int, n)
for i := 0; i < n; i++ {
var tmp int
fmt.Scan(&tmp)
nums[i] = tmp
}
res := quickSort(nums)
for _, num := range res {
fmt.Print(num, " ")
}
}
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static int[] array;
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
array = new int[n];
for (int i = 0; i < n; i++) array[i] = scanner.nextInt();
// apiSort();
// bubbleSort();
// selectSort();
// insertSort();
// heapSort();
// mergeSort(0, n - 1);
quickSort(0, n - 1);
for (int i : array) System.out.print(i + " ");
}
// 使用Java APi
static void apiSort() {
Arrays.sort(array);
}
// 交换两个数
static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 冒泡排序
static void bubbleSort() {
// 每趟往前归位一个最小值
for (int i = 1; i < n; i++)
for (int j = n - 1; j >= i; j--)
if (array[j] < array[j - 1]) swap(j, j - 1);
}
// 选择排序
static void selectSort() {
for (int i = 0; i < n - 1; i++) {
int k = i;
for (int j = i; j <= n - 1; j++)
if (array[j] < array[k]) k = j;
swap(k, i);
}
}
// 插入排序
static void insertSort() {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) swap(j, j - 1);
else break;
}
}
}
// 堆排序
static void heapSort() {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i : array) minHeap.add(i);
for (int i = 0; i < n; i++) array[i] = minHeap.poll();
}
// 归并排序
static void mergeSort(int i, int j) {
if (i >= j) return;
int mid = (i + j) >> 1;
mergeSort(i, mid);
mergeSort(mid + 1, j);
merge(i, mid, j);
}
static void merge(int i, int mid, int j) {
int[] temp = new int[n];
int l = i;
int r = mid + 1;
int t = i;
while (l <= mid && r <= j) temp[t++] = array[l] <= array[r] ? array[l++] : array[r++];
while (l <= mid) temp[t++] = array[l++];
while (r <= j) temp[t++] = array[r++];
System.arraycopy(temp, i, array, i, j - i + 1);
}
// 快速排序
static void quickSort(int i, int j) {
if (i >= j) return;
int pivot = partition(i, j);
quickSort(i, pivot - 1);
quickSort(pivot + 1, j);
}
static int partition(int i, int j) {
int v = array[i];
int l = i + 1;
int r = j;
while (true) {
while (l <= j && array[l] <= v) l++;
while (r >= i + 1 && array[r] >= v) r--;
if (l > r) break;
swap(l++, r--);
}
swap(i, r);
return r;
}
} #include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int n, a[101];
while(scanf("%d", &n)!=EOF) {
for(int i=0; i<n; i++) scanf("%d", &a[i]);
sort(a, a+n);
for(int i=0; i<n; i++) printf("%d ", a[i]);
printf("\n");
}
return 0;
} import java.util.*;
public class Main{
public static void quickSort(int[] arr, int first, int last){
if(first >= last) return;
int pivot = arr[first], l = first, h = last;
while(l < h){
while(l < h && pivot <= arr[h]) h--;
arr[l] = arr[h];
while(l < h && pivot >= arr[l]) l++;
arr[h] = arr[l];
}
arr[l] = pivot;
quickSort(arr, first, l - 1);
quickSort(arr, l + 1, last);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int[] arr = new int[101];
while(in.hasNext()){
int n = in.nextInt();
for(int i = 0; i < n; i++){
arr[i] = in.nextInt();
}
quickSort(arr, 0, n-1);
for(int i = 0; i < n; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
}
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 102;
int num[maxn] = {0};
int main()
{
int n;
while(cin >> n)
{
for(int i = 0; i < n; ++i)
{
cin >> num[i];
}
sort(num, num+n);
for(int i = 0; i < n; ++i)
{
cout << num[i] << " ";
}
cout << endl;
}
return 0;
}
#include<bits/stdc++.h> //万能头
using namespace std;
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> m[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (m[j] > m[j + 1]) {
int temp = m[j];
m[j] = m[j + 1];
m[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << m[i] << " ";
}
}
return 0;
} #include<bits/stdc++.h>
using namespace std;
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> m[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i] > m[j]) {
int temp = m[i];
m[i] = m[j];
m[j] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << m[i] << " ";
}
}
return 0;
}
3.内置sort函数 #include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int m[100];
while(cin>>n){
for(int i=0;i<n;i++){
cin>>m[i];
}
sort(m,m+n); //需要调用#include<algorithm>
for(int i=0;i<n;i++){
cout<<m[i]<<" ";
}
}
return 0;
} 4.手动快速排序qsort函数 #include<bits/stdc++.h>
using namespace std;
int cmp(const void*a,const void*b) {
return *(int*)a - *(int*)b;//升序
//return *(int*)a - *(int*)b;//降序
}
int main() {
int n;
int m[100];
while (cin >> n) {
for (int i = 0; i<n; i++) {
cin >> m[i];
}
qsort(m, n,sizeof (m[0]),cmp);//需要调用#include<algorithm>
for (int i = 0; i<n; i++) {
cout << m[i] << " ";
}
}
return 0;
} #include <iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
int i,j,a[100];
for(i=0;i<n;i++)
cin>>a[i];
//选择排序
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]>a[j]){
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
//冒泡排序
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
while(cin>>n){
int i,j,a[100];
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
//int* simple_swap_sort(int *a,int n); //简单的交换排序
//int* bubble_sort(int* a,int n); //冒泡排序
//int* simple_select_sort(int *a,int n); //简单的选择排序
//int* simple_insert_sort(int *a,int n); //简单的插入排序
//int* shell_sort(int *a,int n); //希尔排序
//int* merge_sort(int *a,int n); //归并排序配合合并函数使用 ps:这递归写的好烂
//int* merge(int *a,int *b,int a_n,int b_n);
int* quick_sort(int *a,int n); //快速排序
void Print(int a[],int n); //输出函数
int main(){
int n,value;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++){
cin>>value;
arr[i]=value;
}
Print(quick_sort(arr,n),n);
// Print(merge_sort(arr,n),n);
// Print(shell_sort(arr,n),n);
// Print(simple_insert_sort(arr,n),n);
// Print(simple_swap_sort(arr,n),n);
// Print(simple_select_sort(arr,n),n);
// Print(bubble_sort(arr,n),n);
delete []arr;
return 0;
}
int* quick_sort(int *a,int n){
if(n<1)
return a;
int i=0,j=n-1;
int temp=*a,change;
while(i<j){
while(*(a+j)>=temp&&i<j){
--j;
}
while(*(a+i)<=temp&&i<j){
++i;
}
if(i<j){
change=*(a+i);
*(a+i)=*(a+j);
*(a+j)=change;
}
}
*a=*(a+i);
*(a+i)=temp;
quick_sort(a,i);
quick_sort(a+i+1,n-i-1);
return a;
}
//int* merge(int *a,int *b,int a_n,int b_n){
// int i=0,j=0,n=0,len=a_n+b_n;
// int* result=new int[len];
// while(i<a_n&&j<b_n){
// if(a[i]<b[j]){
// result[n]=a[i];
// ++i;
// ++n;
// }else{
// result[n]=b[j];
// ++j;
// ++n;
// }
// }
// while(i<a_n){
// result[n]=a[i];
// ++i;
// ++n;
// }
// while(j<b_n){
// result[n]=b[j];
// ++j;
// ++n;
// }
// for(int i=0;i<len;++i){
// *(a+i)=result[i];
// }
// delete[] result;
// return a;
//}
//int* merge_sort(int *a,int n){
// if(n<2){
// return a;
// }
// int *right=a;
// int *left=a+n/2;
// merge_sort(right,n/2);
// merge_sort(left,n-n/2);
// merge(right,left,n/2,n-n/2);
// return a;
//}
//int* shell_sort(int *a,int n){
// int k,temp;
// for(int gap=n/2;gap>0;gap/=2){
// for(int i=0;i<gap;++i){
// for(int j=i;j<n;j+=gap){ //内层是插入排序
// temp=*(a+j);
// for(k=j;(k>i)&&(*(a+k-gap)>temp);k-=gap){
// *(a+k)=*(a+k-gap);
// }
// *(a+k)=temp;
// }
// }
// }
// return a;
//}
//int* simple_insert_sort(int *a,int n){
// int temp,k;
// for(int i=1;i<n;++i){
// temp=*(a+i);
// for(k=i;(*(a+k-1)>temp)&&(k>0);--k){
// *(a+k)=*(a+k-1);
// }
// *(a+k)=temp;
// }
// return a;
//}
//int* simple_select_sort(int *a,int n){
// int temp,min;
// for(int i=0;i<n;++i){
// min=i;
// for(int j=i;j<n;++j){
// if(*(a+min)>*(a+j)){
// min=j;
// }
// }
// temp=*(a+i);
// *(a+i)=*(a+min);
// *(a+min)=temp;
// }
// return a;
//}
//int* bubble_sort(int* a,int n){
// int temp;
// for(int i=0;i<n;++i){
// int flag=0;
// for(int j=0;j<n-i-1;++j){
// if(*(a+j)>*(a+j+1)){
// temp=*(a+j);
// *(a+j)=*(a+j+1);
// *(a+j+1)=temp;
// ++flag;
// }
// }
// if(!flag)
// break;
// }
// return a;
//}
//int* simple_swap_sort(int *a,int n){
// int temp;
// for(int i=0;i<n;++i){
// for(int j=i;j<n;++j){
// if(*(a+i)>*(a+j)){
// temp=*(a+j);
// *(a+j)=*(a+i);
// *(a+i)=temp;
// }
// }
// }
// return a;
//}
void Print(int a[],int n){
for(int i=0;i<n;++i){
cout<<a[i]<<' ';
}
cout<<endl;
}
/** * 快速排序 * 第一记录为枢轴 * @param a 需要排序的数组 * @param low 数组的起始下标 * @param high 数组的末尾下标 */public static void QSort(int a[], int low, int high) { if(low >= high) return; int pivot = a[low], l = low, h = high; for(; l < h; ) { for(; l < h && a[h] >= pivot; h--); a[l] = a[h]; for(; l < h && a[l] <= pivot; l++); a[h] = a[l]; } a[l] = pivot; QSort(a, low, l - 1); QSort(a, l + 1, high); }