8 common sorting of Java
6. Quick sort 8 sorting that programmers must know (Java implementation)
Relationships among 8 sorts:
1. Direct insertion sorting
(1) basic idea:
In a group of numbers to be sorted, assuming that the previous (n-1) [n > = 2] numbers are already in good order, now insert the nth number into the previous ordinal number so that the N numbers are also in good order. Repeat this cycle until all are in order.
(2) examples
(3) implemented in Java
package com.njue;
public class insertSort {
public insertSort(){
inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,15,35,25,53,51};
int temp=0;
for(int i=1;i<a.length;i++){
int j=i-1;
temp=a[i];
for(;j>=0&&temp<a[j];j--){
a[j+1]=a[j]; //将大于temp的值整体后移一个单位
}
a[j+1]=temp;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
2. Hill sort (minimum incremental sort)
(1) basic idea:
The algorithm first divides a group of numbers to be sorted into several groups according to a certain increment D (n / 2, n is the number of numbers to be sorted), and the subscript difference of records in each group is d. all elements in each group are directly inserted and sorted, and then a smaller increment is used (D / 2) group them, and then perform direct insertion sorting in each group. When the increment is reduced to 1, the sorting is completed after direct insertion sorting.
(2) examples:
(3) implemented in Java
public class shellSort {
public shellSort(){
int a[]={1,6,3,45,100};
double d1=a.length;
int temp=0;
while(true){
d1= Math.ceil(d1/2);
int d=(int) d1;
for(int x=0;x<d;x++){
for(int i=x+d;i<a.length;i+=d){
int j=i-d;
temp=a[i];
for(;j>=0&&temp<a[j];j-=d){
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
if(d==1)
break;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
3. Simple selection and sorting
(1) basic idea:
In a group of numbers to be sorted, select the smallest number to exchange with the number at the first position; Then, among the remaining numbers, find the smallest number to exchange with the number in the second position, and cycle until the penultimate number is compared with the last number.
(2) examples:
(3) implemented in Java
public class selectSort {
public selectSort(){
int a[]={1,45};
int position=0;
for(int i=0;i<a.length;i++){
int j=i+1;
position=i;
int temp=a[i];
for(;j<a.length;j++){
if(a[j]<temp){
temp=a[j];
position=j;
}
}
a[position]=a[i];
a[i]=temp;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
4. Heap sorting
(1) basic idea:
Heap sort is a tree selection sort, which is an effective improvement on direct selection sort.
The definition of heap is as follows: a sequence with n elements (H1, H2,..., HN) is called heap if and only if it satisfies (HI > = h2i, hi > = 2I + 1) or (HI < = h2i, hi < = 2I + 1) (I = 1,2, n / 2). Only the heap satisfying the former condition is discussed here. As can be seen from the definition of heap, The top element (i.e. the first element) must be the largest item (large top heap). A complete binary tree can intuitively represent the structure of the heap. The top of the heap is the root, and the others are the left and right subtrees. Initially, the sequence of numbers to be sorted is regarded as a binary tree stored in sequence. Adjust their storage order to make it a heap. At this time, the number of root nodes of the heap is the largest. Then, exchange the root node with the last node of the heap. Then The previous (n-1) number is readjusted to make it a heap. And so on, until the heap with only two nodes, exchange them, and finally get an ordered sequence with n nodes. From the description of the algorithm, heap sorting requires two processes: one is to establish the heap, and the other is to exchange the position between the top of the heap and the last element of the heap. So heap sorting consists of two functions. One is the penetration function of heap building, and the other is the function of repeatedly calling the penetration function to realize sorting.
(2) examples:
Initial sequence: 46,79,40,84
Build up:
Swap, kicking the maximum number from the heap
The remaining nodes rebuild the heap and exchange the maximum number of kicks
And so on: the last two remaining nodes in the last heap are exchanged, one is kicked out, and the sorting is completed.
(3) implemented in Java
import java.util.Arrays;
public class HeapSort {
int a[]={49,51};
public HeapSort(){
heapSort(a);
}
public void heapSort(int[] a){
System.out.println("开始排序");
int arrayLength=a.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(a,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(a,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
private void swap(int[] data, int i, int j) {
// TODO Auto-generated method stub
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
//对data数组从0到lastIndex建大顶堆
private void buildMaxHeap(int[] data, int lastIndex) {
// TODO Auto-generated method stub
//从lastIndex处节点（最后一个节点）的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
}
5. Bubble sorting
(1) basic idea:
In a group of numbers to be sorted, compare and adjust the two adjacent numbers from top to bottom for all the numbers within the range that have not been sorted, so that the larger number sinks and the smaller number rises. That is, whenever two adjacent numbers are compared and their sorting requirements are found to be opposite, they will be exchanged.
(2) examples:
(3) implemented in Java
public class bubbleSort {
public bubbleSort(){
int a[]={49,51};
int temp=0;
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
6. Quick sort
(1) basic idea:
Select a reference element, usually the first element or the last element, and divide the sequence to be arranged into two parts through one scan. One part is smaller than the reference element and one part is greater than or equal to the reference element. At this time, the reference element is in the correct position after it is arranged, and then recursively sort the divided two parts in the same way.
(2) examples:
(3) implemented in Java
public class quickSort {
int a[]={49,51};
public quickSort(){
quick(a);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
public int getMiddle(int[] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}
public void _quickSort(int[] list, int high) {
if (low < high) {
int middle = getMiddle(list, low, high); //将list数组进行一分为二
_quickSort(list, middle - 1); //对低字表进行递归排序
_quickSort(list, middle + 1, high); //对高字表进行递归排序
}
}
public void quick(int[] a2) {
if (a2.length > 0) { //查看数组是否为空
_quickSort(a2, 0, a2.length - 1);
}
}
}
7. Merge and sort
(1) basic sorting:
Merge sorting method is to merge two (or more) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered, and then merge the ordered subsequences into an overall ordered sequence.
(2) examples:
(3) implemented in Java
import java.util.Arrays;
public class mergingSort {
int a[]={49,51};
public mergingSort(){
sort(a,a.length-1);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
public void sort(int[] data, int left, int right) {
// TODO Auto-generated method stub
if(left<right){
//找出中间索引
int center=(left+right)/2;
//对左边数组进行递归
sort(data,left,center);
//对右边数组进行递归
sort(data,center+1,right);
//合并
merge(data,center,right);
}
}
public void merge(int[] data, int center, int right) {
// TODO Auto-generated method stub
int [] tmpArr=new int[data.length];
int mid=center+1;
//third记录中间数组的索引
int third=left;
int tmp=left;
while(left<=center&&mid<=right){
//从两个数组中取出最小的放入中间数组
if(data[left]<=data[mid]){
tmpArr[third++]=data[left++];
}else{
tmpArr[third++]=data[mid++];
}
}
//剩余部分依次放入中间数组
while(mid<=right){
tmpArr[third++]=data[mid++];
}
while(left<=center){
tmpArr[third++]=data[left++];
}
//将中间数组中的内容复制回原数组
while(tmp<=right){
data[tmp]=tmpArr[tmp++];
}
System.out.println(Arrays.toString(data));
}
}
8. Cardinality sorting
(1) basic idea:
All values to be compared (positive integers) are unified into the same digit length, and the numbers with shorter digits are preceded by zeros. Then, start from the lowest bit and sort in turn. In this way, the sequence will become an ordered sequence from the lowest bit to the highest bit.
(2) examples:
(3) implemented in Java
import java.util.ArrayList;
import java.util.List;
public class radixSort {
int a[]={49,101,51};
public radixSort(){
sort(a);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
public void sort(int[] array){
//首先确定排序的趟数;
int max=array[0];
for(int i=1;i<array.length;i++){
if(array[i]>max){
max=array[i];
}
}
int time=0;
//判断位数;
while(max>0){
max/=10;
time++;
}
//建立10个队列;
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<array.length;j++){
//得到数字的第time+1位数;
int x=array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
ArrayList<Integer> queue2=queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count=0;//元素计数器;
//收集队列元素;
for(int k=0;k<10;k++){
while(queue.get(k).size()>0){
ArrayList<Integer> queue3=queue.get(k);
array[count]=queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}