缺失：希尔排序、堆排序
优化：快速排序
待补充状态
导读
简单算法：冒泡排序O(n2)、简单选择排序O(n2)、直接插入排序O(n2)
改进算法：归并排序O(nlogn)、快速排序(冒泡排序优化)O(nlogn)、计数排序、基数排序或桶子法、希尔排序(插入排序优化)O(n3/2)、堆排序(选择排序优化)O(nlogn)
1. 排序问题
1.0 直接使用Arrays.sort(数组名)方法进行排序
int[] d={123,456,19};
Arrays.sort(d);
但有时需要我们使用算法实现，则基本排序常用方法如下：
public static void main(String[] args) {
int[] num = {230,229,8,0,26,25,224,223};
bubbleSort(num); //1.1 冒泡排序
selectSort(num); //1.2 选择排序
insertSort(num); //1.3 插入排序
mergeSort(num); //1.4 归并排序
quickSort(num); //1.5 快速排序
Arrays.toString(num); //打印数组
}
1.1 冒泡排序：BubbleSort
冒泡排序主要是比较相邻的两位数字，取较大值与下一位比较，直至到最高位，完成一轮；第二轮比较至次高位，以此类推
public static void bubbleSort(int[] num) {
for (int i = num.length - 1，temp=0; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (num[j] > num[j + 1]) {
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
}
1.2 选择排序：SelectSort
选择排序，首先选出最小值放在第一位；第二轮选出次小值放在第二位，以此类推
public static void selectSort(int[]num) {
for (int i = 0,temp=0; i < num.length-1; i++) {
for(int j=i+1;j<num.length;j++){
if(num[i]>num[j]){
temp = num[j];
num[j] = num[i];
num[i] = temp;
}
}
}
}
1.3 插入排序：InsertSort
先选定第二个数为标记数，当且仅当第一个数大于等于标记数时，才循环，交换标记数与第一个数的位置，此时设置第一个数为标记数；以此类推
public static void insertSort(int[]num) {
for (int i = 1,temp=0,j=0; i < num.length; i++) {
temp=num[i];
j=i;
while(j>0&&num[j-1]>temp){
num[j]=num[j-1];
num[j-1]=temp;
j--;
}
}
}
1.4 归并排序：MergeSort
分治策略；序列一分为二，然后对子序列进行递归排序，最后合并有序子序列
public static void mergeSort(int[]num){
sort(num,0,num.length-1);
}
public static void sort(int[]num,int left,int right){
if(left<right){
int center=(left+right)>>1;
sort(num,left,center);
sort(num,center+1,right);
merge(num,left,center,right);
}
}
public static void merge(int[]num,int left,int center,int right){
//创建临时数组，暂存数据
int[] tmpArr=new int[num.length];
int third=left;
int temp=left;
int mid=center+1;
//对两个子序列中取出较小的放入临时数组，直至某子序列全部放完
while(left<=center&&mid<=right){
if(num[left]<=num[mid]){
tmpArr[third++]=num[left++];
}else{
tmpArr[third++]=num[mid++];
}
}
//此处两个while只能运行一个
while(mid<=right){
tmpArr[third++]=num[mid++];
}
while(left<=center){
tmpArr[third++]=num[left++];
}
//此处把数据从临时数组中复制回原数组
while(temp<=right){
num[temp]=tmpArr[temp++];
}
}
1.5 快速排序
以数组中的某位随机数为比较值key，从右、左分别向中间逼近，一次排序把小于比较值key的放在左边，大于比较值key的放在右边，然后再对两边子序列分别进行排序，以此类推
1.5.1 基本快速排序：QuickSort
以数组中的首数或尾数为比较值key：
public static void quickSort(int[]num){
if(num==null||num.length<=0){
System.out.println("error data");
return;
}
sort(num,0,num.length-1);
}
public static void sort(int[] num,int left,int right){
if(left<right){
int center=getMiddle(num,left,right);
sort(num,left,center-1);
sort(num,center+1,right);
}
}
public static int getMiddle(int[] num,int left,int right){
int tmp=num[left];
while(left<right){
//两个while分别从右、左向中间逼近
while(left<right&&tmp<=num[right]){
right--;
}
if(left<right){
num[left]=num[right];
left++;
}
while(left<right&&num[left]<=tmp){
left++;
}
if(left<right){
num[right]=num[left];
right--;
}
}
num[left]=tmp;
return left;
}
1.5.2 随机化快速排序：RandomQuickSort
随机设定比较值key：
public static void randomQuickSort(int[] num) {
if (num == null || num.length <= 0) {
System.out.println("error data");
return;
}
sort(num, 0, num.length - 1);
}
public static void sort(int[] num, int left, int right) {
if (left < right) {
int middle = randomNum(num, left, right); //内容有变动
sort(num, left, middle - 1);
sort(num, middle + 1, right);
}
}
//新增方法
public static int randomNum(int[] num, int left, int right) {
//获取left与right中间的任意随机值
int random = (int) (left + Math.random() * (right - left));
int temp = num[left];
num[left] = num[random];
num[random] = temp;
return getMiddle(num, left, right);
}
public static int getMiddle(int[] num, int left, int right) {
int tmp = num[left];
while (left < right) {
while (left < right && tmp <= num[right]) {
right--;
}
if (left < right) {
num[left] = num[right];
left++;
}
while (left < right && num[left] <= tmp) {
left++;
}
if (left < right) {
num[right] = num[left];
right--;
}
}
num[left] = tmp;
return left;
}
1.6 计数排序：CountSort
统计数组中的各数出现的次数，然后再安排先后顺序一一打印出来
public static void countSort(int[] num) {
if(num==null||num.length<=0){
System.out.println("error data");
return;
}
int max=0,min=0;
for(int i=0;i<=num.length-1;i++){
if(num[i]<min){
min=num[i];
}
if(num[i]>max){
max=num[i];
}
}
int [] newNum=new int[max-min+1];
for(int i=0;i<=num.length-1;i++){
newNum[num[i]-min]++;
}
int count=0;
for(int i=0;i<newNum.length;i++){
while(newNum[i]>0){
num[count++]=min+i;
newNum[i]--;
}
}
}
1.7 基数排序或桶子法：RadixSort 或 BucketSort
1.7.1 LSD法
最低位优先(Least Significant Digit first)法：先获取最高位数，然后从低向高依次排序，即个、十、百、千位···
import java.util.List; //导入List集合包
import java.util.ArrayList; //导入ArrayList包
public static void radixSort(int[] num) {
if (num == null || num.length <= 0) {
System.out.println("error data");
return;
}
sort(num);
}
public static void sort(int[] num) {
// 计算数组中最大数k的位数time
int k = num[0], time = 1;
for (int i = 0; i < num.length; i++) {
k = k < num[i] ? num[i] : k;
}
while (k / 10 != 0) {
time++;
k /= 10;
}
// 创建0-9个ArrayList存放数据
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
// 进行time次分配
for (int i = 0; i < time; i++) {
for (int j = 0; j < num.length; j++) {
int x = num[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(num[j]);
queue.set(x, queue2);
}
// printqueue(queue); //打印list数组
int count = 0;
// 收集队列元素
for (int m = 0; m < 10; m++) {
for (int t = 0; t < queue.get(m).size(); t++) {
num[count++] = (int) queue.get(m).get(t);
}
queue.get(m).clear();
}
}
}
1.7.2 MSD法
最高位优先(Most Significant Digit first)法：先获取最高位数，然后依次从高位到低位进行排序；即···千、百、十、个位
暂时缺失
## 排序的稳定性与不变性
#### 不变性
在算法运行时保持不变的条件
#### 稳定性
如果具有相同关键字的数据项，经过排序它们的顺序保持不变，这样的排序就是稳定的
网友评论