JAVA 의 각종 정렬 사상 과 예시
19701 단어 자바
번호
명칭.
의 원리
1
거품 정렬
거품 정렬 정렬 원리:2 층 순환 제어,외층 순환 을 통 해 i 층 의 수 를 제어 하고 남 은 데이터 에서 가장 작 거나 가장 큰 것 을 찾 습 니 다. 내부 순환 은 아래 표 시 된 두 수의 크기 를 순서대로 비교 하고 소수 나 큰 수의 위 치 를 교체 하 는 것 을 책임 진다. 매번 비교 할 때마다 지난번 메모리 에서 교 체 된 새 그룹 비교 입 니 다.
2
정렬 선택
정렬 선택 배열 의 이전 요소 와 뒤의 요소 의 크기 를 비교 하고 뒤의 요소 가 앞의 요소 보다 작 으 면 하나의 변수 k 로 그의 위 치 를 기억 합 니 다. 이 어 두 번 째 비 교 를 통 해 앞의'뒤의 요소'는'앞의 요소'가 되 었 고 그의'뒤의 요소'와 계속 비교 했다.만약 에 뒤의 요소 가 그 보다 작다 면 변수 k 로 배열 에 있 는 위치(아래 표)를 기억 하고 순환 이 끝 날 때 우 리 는 가장 작은 수의 아래 표를 찾 은 다음 에 판단 해 야 한다.만약 이 원소 의 아래 표 가 첫 번 째 원소 의 아래 표 가 아니라면, 첫 번 째 요 소 를 그 와 값 을 교환 하 게 하면 전체 배열 에서 가장 작은 수 를 찾 을 수 있다.그리고 배열 의 두 번 째 작은 수 를 찾 아 배열 의 두 번 째 요소 와 값 을 교환 하 라 고 한다. a)첫 번 째 순환:첫 번 째 수의 아래 표 시 를 기록 하 는 b)첫 번 째 수의 값 을 뒤의 값 에 비해 뒤의 값 보다 크 면 아래 표 시 를 뒤의 값 에 대응 하 는 아래 표 시 를 바 꿉 니 다.c） 첫 번 째 순환 이 끝 난 후에 아래 표 시 된 값 이 바 뀌 면 다음 에 이 수치 보다 작은 요소 가 있 음 을 설명 하고 이들 의 위 치 를 교환 합 니 다 d)상기 조작 을 반복 합 니 다.모든 수치 가 정렬 될 때 까지.
3
삽입 정렬
정렬 기본 사상 삽입:정렬 할 그룹 수 에서 앞(n-1)[n>=2]개 수 는 이미 줄 이 라 고 가정 합 니 다. 좋 은 순서 입 니 다.지금 은 n 번 째 수 를 앞 에 있 는 서수 에 꽂 아서 이 n 번 째 수도 순 서 를 정 해 야 합 니 다.이렇게 모든 순서 가 정 해 질 때 까지 반복 한다.
4
힐 정렬
기본 사상: n 보다 작은 정수 d1 을 첫 번 째 증분 으로 하고 파일 의 모든 기록 을 d1 그룹 으로 나 눕 니 다.모든 거 리 는 dl 의 배수 로 같은 그룹 에 기록 되 어 있 습 니 다.먼저 각 그룹 내 에서 직접 삽입 정렬 하기;그 다음 에 두 번 째 증 량 d2
빠 른 정렬
빠 른 정렬 의 원리 한 배열 에 대해 서 는 어떤 key 값 에 따라 나 누 어 집 니 다. key 값 왼쪽 의 수 는 key 보다 통일 되 고 key 값 오른쪽 은 key 보다 통일 된다. 그리고 양쪽 배열 을 재 귀적 으로 정렬 합 니 다. 최종 결 과 는 전체적으로 질서 가 있다. 키 값 의 점 을 어떻게 찾 습 니까?기본 값 은 마지막 값 으로 구분 합 니 다.
6
통 정렬
통 정렬(Bucket sort)이나 상자 정렬 이란 정렬 알고리즘 입 니 다.작업 의 원 리 는 한 정 된 수량의 통 에 배열 하 는 것 입 니 다.각 통 마다 개별적 으로 정렬 합 니 다.통 정렬 은 비둘기 둥지 정렬 의 귀납 적 결과 이다.정렬 할 배열 의 수치 가 고 르 게 분 배 될 때 통 정렬 은 선형 시간(Θ（n））。그러나 통 정렬 은 비교적 정렬 된 것 이 아니 라 O(n log n)하한 선의 영향 을 받 지 않 는 다.
7
더미 정렬
퇴적 정렬(Heapsort)은 퇴적 트 리(퇴적)라 는 자료 구 조 를 이용 해 디자인 된 정렬 알고리즘 으로,배열 의 특성 을 이용 해 지 정 된 색인 을 빠르게 찾 을 수 있 는 요 소 를 말한다.쌓 기 정렬 은 불안정 한 정렬 방법 으로 보조 공간 은 O(1)이 고 최 악의 시간 복잡 도 는 O(nlog2n)이 며 쌓 기 정렬 의 평균 성능 은 최 악의 성능 에 가깝다.
8
정렬
병합 정렬 은 재 귀 와 분 리 된 기술 을 이용 하여 데이터 서열 을 점점 작은 반 자 표 로 나 누고 반 자 표 에 대해 정렬 하 는 것 이다.마지막 으로 재 귀 절차 로 정렬 된 반 자 표를 합 쳐 점점 더 큰 질서 있 는 서열 로 만 드 는 것 이다.병합 정렬 은 두 가지 절 차 를 포함한다.
9
기수 정렬
(radix sort)는'분배 식 정렬'(distributionsort)에 속 하 며,기수 정렬 법 은'통 법'(bucket sort)또는 bin sort 라 고도 부른다.말 그대로 키 값 의 일부 정 보 를 통 해 정렬 할 요 소 를 일부'통'에 배분 하여 정렬 하 는 역할 을 한다.기수 정렬 법 은 안정성 있 는 정렬 에 속한다.그 시간 복잡 도 는 O(nlog(r)m)이 고 그 중에서 r 는 취 하 는 기수 이 며 m 는 더미 이다.어떤 때 는 기수 정렬 법의 효율 이 다른 비교 적 정렬 법 보다 높다.
package com.sanjiesanxian.sort.test;
/**
*
* **/
public class AllSort {
static int datas[] = { 5, 2, 1, 3, 6,100,0,-9,999,12 };
public static void main(String[] args) {
// bubbleSort();
// selectSort();
//insertSort();
// / print(" ", datas);
//shellSort1(datas, datas.length);
//quickSort(datas, 0, datas.length-1);
//print("
", datas);
}
/**
* @param a
* @param n
*
* **/
public static void shellSort1(int []a,int n){
//gap ，
for(int gap=n/2;gap>0;gap/=2){
// gap ,
for(int i=0;i<gap;i++){
for(int j=i+gap;j<n;j+=gap){
// a[j]<a[j-gap]. a[j] ，
if(a[j]<a[j-gap]){
int tmp=a[j];
int k=j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=tmp;
}
}
}
}
}
/**
*
*
*
* @param a
* @param n
* @param i
* @param gap
*
* 2
*
* **/
public static void groupSort(int[] a,int n,int i,int gap){
for(int j=i+1;j<n;j+=gap){
// a[j]<a[j-gap]. a[j] ，
if(a[j]<a[j-gap]){
int tmp=a[j];
int k=j-gap;
while(k>=0&&a[k]>tmp){
a[k+gap]=a[k];
k-=gap;
}
a[k+gap]=tmp;
}
}
}
/**
* ，
* @param a
* @param n
*
* */
public static void shellSort2(int []a ,int n){
//gap ，
for(int gap=n/2;gap>0;gap/=2){
// gap ，
for (int i = 0; i < gap; i++) {
groupSort(a, n, i, gap);
}
}
}
/**
*
*
* ： ， ， i ，
* ， ，
*
* ，
*
* **/
public static void bubbleSort() {
System.out.print(" ： ");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println();
for (int i = 0; i < datas.length; i++) {
for (int j = i + 1; j < datas.length; j++) {
int temp = 0;
System.out.println("i=" + i + " datas[i]=" + datas[i] + " , "
+ "j=" + j + " datas[j]=" + datas[j]);
if (datas[i] > datas[j]) {
temp = datas[j];
datas[j] = datas[i];
datas[i] = temp;
}
System.out.print(" : ");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println("");
}
System.out.println("
=========== =============");
for (int t : datas) {
System.out.print(t + " ");
}
System.out.println("");
}
// System.out.print(" ： ");
// for(int t:datas){
// System.out.print(t+" ");
// }
}
/**
*
*
*
* ， key ，
* key ， key，key key
* ，
*
*
* key ，
*
*
*
*
*
*
*
* @param arr
* @param from
* @param to
*
* **/
public static void quickSort(int arr[],int from ,int to){
//1,5,2,4
if(from<to){// form<to ，
int temp=arr[to];//temp
int i=from-1;//i -1；
for(int j=from;j<to;j++){//j=0；j to，j++
if(arr[j]<=temp){// arr[j]
i++;//i++；0
int tempValue=arr[j];
arr[j]=arr[i];
arr[i]=tempValue;
}
// print("
", arr);
}
arr[to]=arr[i+1];
arr[i+1]=temp;
//System.out.println(" : "+arr[i]);
quickSort(arr, from, i);
quickSort(arr, i+1, to);
}
}
/**
*
* **/
public static void print(String info, int datas[]) {
System.out.print(info + ": ");
for (int i : datas) {
System.out.print(i + " ");
}
}
/**
*
*
* ， k ，
* ， “ ” “ ”， “ ”
* k ( )， ， ， ， ，
* ， 。 ， ， 。
*
*
* a） ： b） 、 、 。 c）
* 、 、 、 d） 、
*
*
*
*
*
* **/
public static void selectSort() {
print(" ", datas);
for (int i = 0; i < datas.length; i++) {
int lowIndex = i;//
for (int j = i + 1; j < datas.length; j++) {
if (datas[j] < datas[lowIndex]) {
lowIndex = j;
}
}
// lowindex i ，
if (lowIndex != i) {
int temp = datas[i];
datas[i] = datas[lowIndex];//
datas[lowIndex] = temp;//
}
// print("
", datas);
}
print("
", datas);
}
/**
* ： ， (n-1) [n>=2]
* ， n ， n
* 。 ， 。
*
*
*
* **/
public static void insertSort() {
print(" : ", datas);
for (int i = 0; i < datas.length; i++) {
//
int insertVal = datas[i];
// ，
int index = i - 1;
while (index >= 0 && datas[index] > insertVal) {
// ， ， ， ，
//
datas[index + 1] = datas[index];
index--;
}
datas[index + 1] = insertVal;
print("
: ", datas);
}
print("
: ", datas);
}
}
package com.sanjiesanxian.sort.test;
/**
*
*
* */
public class BucketSort {
/**
*
* @param a
* @param max a
* **/
public static void bucketSort(int[] a,int max){
int buckets[];
if(a==null||max<1){
return;
}
// max buckets， buckets 0
buckets=new int[max];
//1，
for(int i=0;i<a.length;i++){
buckets[a[i]]++;
}
//
for(int i=0,j=0;i<max;i++){
while((buckets[i]--)>0){
a[j++]=i;
}
}
buckets=null;
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
public static void main(String[] args) {
//
int a[]={1,5,2,88,9};
print(" : ", a);
bucketSort(a, 89);
print(" : ", a);
}
}
package com.sanjiesanxian.sort.test;
/**
*
*
* **/
public class HeapSort {
/**
*
*
* ， N 2N+1， 2N+2
* ，N ， N 0
*
* @param a
* @param start 0 ，
* @param end
*
* **/
public static void maxHeapDown(int []a ,int start,int end){
int c=start; //
int l=2*c+1; //
int tmp=a[c]; //
for(;l<=end;c=l,l=2*l+1){
//l ，l+1
if(l<end&&a[l]<a[l+1]){//
// if(l<end&&a[l]>a[l+1]){//
l++; // ， _heap[l+1]
}
if(tmp>a[l]){//
//if(tmp<=a[l]){//
break;
}else{
a[c]=a[l];
a[l]=tmp;
}
}
}
/**
*
*
* @param a
* @param n
*
* */
public static void heapSortAsc(int [] a,int n){
int i,tmp;
// (n/2-1)--->0 ， ， ，
for(i=n/2-1;i>=0;i--){
maxHeapDown(a, i, n-1);
}
// ， ， ，
for(i=n-1;i>0;i--){
// a[0] a[i], a[i] 0....i
tmp=a[0];
a[0]=a[i];
a[i]=tmp;
// a[0.....i-1], a[0....i-1]
// , a[i-1] [0...i-1]
maxHeapDown(a, 0, i-1);
}
}
public static void main(String[] args) {
int i;
int a[] = {1,4,-2,2,7,0,5};
print(" :", a);
heapSortAsc(a, a.length);//
print(" :", a);
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
}
package com.sanjiesanxian.sort.test;
/**
*
*
*
* */
public class MergeSort {
/**
*
*
* @param a
* @param start
* @param mid ，
* @param end
*
* */
public static void merge(int []a,int start,int mid,int end){
int []temp=new int[end-start+1];
int i=start; //
int j=mid+1; //
int k=0; //
while(i<=mid&&j<=end){
if(a[i]<=a[j]){
temp[k++]=a[i++];
}else{
temp[k++]=a[j++];
}
}
while(i<=mid){
temp[k++]=a[i++];
}
while(j<=end){
temp[k++]=a[j++];
}
for(i=0;i<k;i++){
a[start+i]=temp[i];
}
temp=null;
}
/**
*
*
* a
* start
* end
*
* */
public static void mergeSortUp2Down(int []a,int start,int end){
if(a==null||start>=end){
return;
}
int mid=(end+start)/2;
mergeSortUp2Down(a, start, mid);// a[start...mid]
mergeSortUp2Down(a, mid+1, end);// a[mid+1...end]
//a[start...mid] [mid+1...end]
// a[start....end]
merge(a, start, mid, end);
}
/***
* a : a len， gap ；
* 2 ，
*
* @param a
* @param len
* @param gap
* **/
public static void mergeGroups(int []a,int len,int gap){
int i;
int twolen=2*gap; //
// 2ge ，
for(i=0;i+2*gap-1<len;i+=(2*gap)){
merge(a, i, i+gap-1, i+2*gap-1);
// i+gap-1< len-1 ,
//
if(i+gap-1<len-1){
merge(a, i, i+gap-1, len-1);
}
}
}
/**
* ( )
*
* @param a
* **/
public static void mergeSortDown2Up(int[]a){
if(a==null){
return;
}
for(int n=1;n<a.length;n*=2){
mergeGroups(a, a.length, n);
}
}
public static void main(String[] args) {
int []a={3,4,-1,44,32,9};
print(" : ", a);
mergeSortUp2Down(a, 0, a.length-1);
print(" : ", a);
}
/**
*
*
* */
private static void print(String info,int arr[]){
System.out.println(info);
for(int a:arr){
System.out.print(a+" ");
}
System.out.println();
}
}
package com.sanjiesanxian.sort.test;
/***
*
*
*
* */
public class RadixSort {
/*
* a
*
* ：
* a --
* n --
*/
private static int getMax(int[] a) {
int max;
max = a[0];
for (int i = 1; i < a.length; i++)
if (a[i] > max)
max = a[i];
return max;
}
/*
* " " ( )
*
* ：
* a --
* exp -- 。 a 。
*
* ， a={50, 3, 542, 745, 2014, 154, 63, 616}；
* (01) exp=1 " " a
* (02) exp=10 " " a
* (03) exp=100 " " a
* ...
*/
private static void countSort(int[] a, int exp) {
//int output[a.length]; // " "
int[] output = new int[a.length]; // " "
int[] buckets = new int[10];
// buckets[]
for (int i = 0; i < a.length; i++)
buckets[ (a[i]/exp)%10 ]++;
// buckets[i]。 buckets[i] ， output[] 。
for (int i = 1; i < 10; i++)
buckets[i] += buckets[i - 1];
// output[]
for (int i = a.length - 1; i >= 0; i--) {
output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
buckets[ (a[i]/exp)%10 ]--;
}
// a[]
for (int i = 0; i < a.length; i++)
a[i] = output[i];
output = null;
buckets = null;
}
/*
*
*
* ：
* a --
*/
public static void radixSort(int[] a) {
int exp; // 。 ，exp=1； ，exp=10；...
int max = getMax(a); // a
// ， a " "
for (exp = 1; max/exp > 0; exp *= 10)
countSort(a, exp);
}
public static void print(String info,int a[]){
System.out.print(info);
for(int aa:a){
System.out.print(aa+" ");
}
System.out.println();
}
public static void main(String[] args) {
//
int a[]={1,5,2,88,9};
print(" : ", a);
radixSort(a);
print(" : ", a);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
