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); }