堆排序
#include <iostream>
using namespace std;
int tempnum;
void KeepCharacter(int *data,int n,int num) //保持性质函数，保证是一个大根推；
{
int left=n*2;
int right=n*2+1;
int max; //记录最大的数字的位置；
if(left<=num&&data[n]<data[left]) //比较根与左孩子大小,挑出一个比较大的数
max=left;
else
max=n;
if(right<=num&&data[max]<data[right]) //比较局部极大值与右孩子，挑出一个最大值
max=right;
if(max!=n)
{
int temp=data[max];
data[max]=data[n];
data[n]=temp;
KeepCharacter(data,max,num); //调整后子树有可能不满足性质，应该递归调用；
}
}
void HeapSort(int *data,int num)
{
for(int i=num/2;i>=1;i--) //建堆调用
KeepCharacter(data,i,num);
for(int i=num;i>=2;i--)
{
int temp=data[1];
data[1]=data[i];
data[i]=temp;
num-=1;
KeepCharacter(data,1,num);
}
}
int main()
{
int num;
cout<<"Please input the num of data:"<<endl;
cin>>num;
cout<<"Please input data:"<<endl;
int *data=new int[num+1];
for(int i=1;i<=num;i++)
cin>>data[i];
for(int i=num/2;i>=1;i--) //建堆调用
KeepCharacter(data,i,num);
HeapSort(data,num);
cout<<"After sorted:"<<endl;
for(int i=1;i<=num;i++)
cout<<data[i]<<" ";
cout<<endl;
}
自底向上的归并排序：
import java.util.Scanner;
public class Merge {
private static int[] aux;
public static void sort(int[] a){
aux = new int[a.length];
sort(a,0,a.length-1);
}
public static void mergefun(int[] a,int lo,int mid,int hi){
int i = lo,j = mid+1;
for(int k = lo;k <= hi; k++)
aux[k] = a[k];
for(int k = lo;k <= hi; k++)
if(i>mid)
a[k] = aux[j++];
else if(j>hi)
a[k] = aux[i++];
else if(a[i]<a[j])
a[k] = aux[j++];
else
a[k] = aux[i++];
}
private static void sort(int[] a,int lo,int hi){
if(hi<=lo)
return;
int mid = lo+(hi-lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
mergefun(a,lo,mid,hi);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arrdata = str.split(" ");
int[] data = new int[arrdata.length];
for(int i = 0;i < arrdata.length; i++)
data[i] = Integer.parseInt(arrdata[i]);
sort(data);
for(int i = 0;i < data.length; i++)
System.out.print(data[i]+" ");
System.out.println();
}
}
希尔排序：
package com.sort;
import java.util.Scanner;
public class Shell {
public static void sort(int[] a){
int n = a.length;
int h = 1;
while(h<n/3) h = h*3+1;
while(h>=1){
for(int i = h; i < n; i++){
for(int j = i; (j >= h)&&(a[j]<a[j-h]);j -= h ){
int temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
h = h/3;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arrdata = str.split(" ");
int[] data = new int[arrdata.length];
for(int i = 0;i < arrdata.length; i++)
data[i] = Integer.parseInt(arrdata[i]);
sort(data);
for(int i = 0;i < data.length; i++)
System.out.print(data[i]+" ");
System.out.println();
}
}
快速排序：
package com.sort;
import java.util.Scanner;
public class Quick {
private static void sort(int[] a,int lo,int hi){
if(hi<=lo)
return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(int[] a, int lo, int hi) {
int i = lo,j = hi+1;
int v = a[lo];
while(true){
while(a[++i]<v)
if(i==hi)
break;
while(v<a[--j])
if(j==lo)
break;
if(i>=j)
break;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int temp2 = a[lo];
a[lo] = a[j];
a[j] = temp2;
return j;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] arrdata = str.split(" ");
int[] data = new int[arrdata.length];
for(int i = 0;i < arrdata.length; i++)
data[i] = Integer.parseInt(arrdata[i]);
sort(data,0,data.length-1);
for(int i = 0;i < data.length; i++)
System.out.print(data[i]+" ");
System.out.println();
}
}
计数排序：
对于一个int数组，请编写一个计数排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
public class CountingSort {
public int[] countingSort(int[] A, int n) {
count(A);
return A;
}
public static void count(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
min = Math.min(arr[i], min);
max = Math.max(arr[i], max);
}
int[] countArr = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < countArr.length; i++) {
while (countArr[i]-- > 0) {
arr[index++] = i + min;
}
}
}
}
桶排序（基数排序）：
对于一个int数组，请编写一个基数排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。
测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
public class radixSortTry {
public int calPos(int data,int k){
for(int i = 1;i < k; i++){
data /=10;
}
return data%10;
}
public int[] radixSort(int[] A,int n){
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
for(int i = 0;i < 10;i++)
list.add(new ArrayList<Integer>());
for(int i = 1;i <= 4; i++){
for(int j = 0;j < n; j++){
list.get(calPos(A[j],i)).add(A[j]);
}
int pos = 0;
for(int j = 0;j<list.size();j++){
int num = list.get(j).size();
for(int k = 0;k<num;k++)
A[pos++] = list.get(j).remove(0);
}
}
return A;
}
public static void main(String[] args) {
int[] A = {54,35,48,36,27,12,44,44,8,14,26,17,28};
radixSortTry t = new radixSortTry ();
t.radixSort(A, 13);
}
}