프로그램 = 자료구조 + 알고리즘. 우리가 작성하지 않은 프로젝트를 구축하는 프레임워크의 경우 실제로 프로젝트 수준을 판단할 수 있는 것은 우리가 사용자 정의한 데이터 구조가 편리하고 간결하며 이러한 방법을 구현하는 데 사용하는 알고리즘이 빠른지 여부입니다. 그리고 효과적입니다. 오류가 발생하기 쉽습니다. 만약 당신이 하고 싶은 일이 매일 아침부터 밤까지 벽돌을 옮기는 일이 아니라면, 알고리즘을 배우고 데이터 구조를 분석하는 것이 확실히 레벨을 높이는 유일한 방법입니다.

(1) 정렬 알고리즘

알고리즘과 프로그래밍 언어는 밀접한 관련이 있지만 특정 언어에만 의존하는 것은 아닙니다. 구현 언어를 고려하지 않고 일반적으로 다음과 같은 정렬 방법을 사용합니다.

선택 정렬

삽입 정렬

힐 정렬

병합 정렬

빠른 정렬

이러한 정렬 방법에 대해서만 이야기하는 것이 아닙니다. 5가지 정렬 알고리즘을 소개한 후 이러한 방법을 요약하고 Java API와 연결해 보겠습니다. 또한 이러한 정렬 방법의 구현을 용이하게 하기 위해 이제 몇 가지 보조 방법을 사용합니다. 이러한 보조 방법은 매우 간단하며 그 목적은 코드를 간결하게 만드는 것입니다.

    /**
     * 比较两个大小不同的数字，如果第一个参数比较小则返回true。
     * 
     * @param v 第一个数字
     * @param w 第二个数字
     * @return 返回比较结果
     */
    public static boolean less(int v , int w){        if(v<w) return true;        return false;
    }    /**
     * 交换数组中两个索引的内容
     * 
     * @param arr 数组
     * @param v 第一个索引
     * @param w 第二个索引
     */ 
    public static void exch(int[] arr,int v ,int w){        int temp=arr[v];
        arr[v]= arr[w];
        arr[w] = temp;
    }    /**
     * 打印数组
     * 
     * @param arr 要显示的数组
     */
    public static void show(int[] arr){        for(int i=0;i<arr.length;i++)
        System.out.println(arr[i]);
    }

로그인 후 복사

(2) 정렬 비용 모델

Java에서는 대부분의 요소가 객체이며 이러한 객체의 기본 키에 대한 설명은 Comparable을 통해 이루어집니다. 메커니즘 이를 달성하기 위해 Comparable에는 순서와 정렬이라는 개념이 있습니다. 그렇다면 정렬 방법이 빠른지 느린지, 얼마나 빠르고 효율적인지 어떻게 연구할 수 있을까요? 우리는 다음과 같은 측면에서 각 정렬 알고리즘의 비용을 연구할 것입니다.

비교하고 교환하기 (정렬 비용을 판단하려면 비교하고 교환한 횟수를 계산해야 함)
시간(정렬 알고리즘에 걸리는 시간, 또는 특정 상황에서 걸리는 시간)
추가 메모리 사용량 ( 일부 정렬 방법에는 추가 메모리 공간이 필요하지만 다른 정렬 방법에는 추가 메모리 공간이 필요하지 않습니다.)

일부 특수 정렬 알고리즘에 대해 특별한 비용 추정 방법을 제공합니다. 대부분의 정렬 방법에 대해 논의합니다. 결국 이 방법이 적합할 때 - 결국 쓸모없는 정렬은 오랫동안 제거되었습니다.

(3) 선택 정렬

선택 정렬은 모든 정렬 중에서 가장 간단한 정렬 알고리즘입니다. 선택 정렬의 핵심 아이디어는 다음과 같습니다.

배열의 앞쪽 끝에 순서가 지정된 하위 배열을 유지하고, 순서가 지정되지 않은 배열의 후반부에서 매번 가장 작은 요소를 찾아 다음과 결합합니다. 프런트 엔드 끝 다음의 첫 번째 요소 순서가 지정되지 않은 요소를 교체하여 이 요소를 순서대로 만듭니다. 정렬된 부분 배열 요소가 전체 요소 수와 같을 때 정렬이 완료됩니다.

일반적인 용어로는 먼저 배열에서 가장 작은 요소를 찾아 첫 번째 요소와 교환합니다. 첫 번째 요소가 가장 작은 요소인 경우 해당 요소와 직접 교체합니다. 🎜>. 그런 다음 두 번째 요소부터 끝까지 가장 작은 요소를 찾아 배열의 두 번째 요소와 교환하는 식으로 계속해서 나머지 요소 중에서 가장 작은 요소를 선택합니다.

1. 비교 및 교환

선택 정렬에는 고정된 비교 횟수

N2^/2가 있습니다. 고정된 교환 횟수N.

비교 횟수 측면에서 선택 정렬에서는 첫 번째 요소부터 마지막 요소까지 처음으로 비교해야 가장 작은 요소가 무엇인지 알 수 있습니다. 두 번째로 가장 작은 요소를 알기 위해서는 N-1 비교가 필요합니다. 총 N+(N-1)+(N-2)+ ··· + 1 = N

2^{/2회가 필요합니다.}

알고리즘 프로그래밍으로 인해 가장 작은 요소가 이미 올바른 위치에 있더라도 위치를 자체적으로 교환해야 하므로 교환 횟수도 N회 고정됩니다.

2. 시간

선택 정렬의 실행 시간은 N

2^{/2회 비교(N}2) 정도로 고정됩니다. ^{/2, 기본적으로 N번의 교환은 무시할 수 있습니다. 정렬 방법의 실행 시간을 예측할 수 없다면 이제 적어도 하나의 보장된 정렬 방법을 알 수 있습니다. 정렬 방법을 올바르게 사용하는 한 실행 시간은 N}2^{/2 비교 횟수를 초과하지 않습니다. .}

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 选择排序
 */public class Sort1 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用选择排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++) {            
    int min = i;            
    for (int j = i + 1; j < arr.length; j++)                
    if (Tool.less(arr[j], arr[min]))
                    min = j;
            Tool.exch(arr, min, i);
        }
    }
}

로그인 후 복사

4.特点

选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。

（四）插入排序

在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：

从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。

我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。

1.比较和交换

在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N²/4次比较以及N²/4次交换。在最坏的情况下需要N²/2次比较和N²/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N²/4的比较和交换次数。

2.时间

我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。

数组中每个元素距离他的最终位置不远
一个有序数组的大数组接一个小数组
数组中只有几个元素的位置不正确

上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 插入排序
 */public class Sort2 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用插入排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++)            
    for (int j = i; j > 0; j--)                
    if (Tool.less(arr[j], arr[j - 1]))
                    Tool.exch(arr, j, j - 1);
    }
}

로그인 후 복사

4.特点

在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：

交换和比较的次数相同

比较的次数大于等于倒置的数量

比较的次数小于等于倒置数量加上数组的大小再减一

除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。

（五）选择算法和插入算法比较

这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。

(6) 힐 정렬

다음에 소개할 정렬 알고리즘은 1차 정렬 알고리즘은 아니지만 실제로 삽입 알고리즘의 기술을 활용한 것이라고 할 수 있습니다. 그럼 여기서 논의해 보세요. 힐 정렬(Hill Sorting)은

큰 것부터 작은 것까지 상수 h 값을 공식화하고 정렬을 삽입하여 배열에서 h 간격의 요소를 정렬하는 것을 말합니다. h=1이 될 때까지 h의 크기를 계속 줄여 전체 배열이 정렬되도록 합니다.

브리지를 비유로 들어보겠습니다. 처음에는 카드 덱이 순서 없이 하나씩 있는데 갑자기 이 방법이 너무 느리다는 느낌이 듭니다. , 그래서 먼저 대략적인 심사를 할 계획입니다. 어떤 카드는 순서대로 넣었는데 다른 카드는 순서가 맞지 않습니다. 이런 식으로 여러 번 카드를 살펴보고 최종적으로 손에 있는 모든 카드를 순서대로 만듭니다. 이것이 힐 정렬이다.

수만 개의 배열을 정렬해야 할 때 일반적으로 Hill 정렬을 사용할 수 있습니다.
Hill 정렬에서는 먼저 h를 정의합니다. h를 하위 배열을 나누기 위한 간격으로 사용합니다. 삽입 알고리즘을 사용하여 이 하위 배열을 정렬합니다. 그런 다음 계속해서 h를 더 작게 만들고 새 배열을 정렬합니다. 마지막으로 h가 1일 때 이 정렬을 통해 모든 데이터가 순서대로 유지됩니다.

1. 장점

그럼 힐 정렬의 장점은 무엇일까요? 삽입 정렬의 장점은 부분적으로 정렬된 시퀀스를 정렬하는 데 매우 빠르며 작은 배열을 정렬하는 데 매우 빠르다는 것입니다. 우리의 Hill 정렬은 이 두 가지 장점을 결합합니다. h가 크면 전체 배열이 상대적으로 작아지고 삽입 정렬이 빨라집니다. h가 작을수록 전체 배열이 점차 질서 있게 됩니다. 이때 삽입 정렬을 사용하는 것도 매우 좋은 선택입니다. Hill 정렬은 이 두 가지 장점을 결합하여 전체 시간이 상대적으로 빠르다고 할 수 있습니다.

2. 시간

Hill 정렬의 경우 다음과 같은 이유로 위의 분석 방법으로 분석하지 않습니다. 우선, Hill 정렬은 교환과 비교를 연구하기가 매우 어렵습니다. 왜냐하면 핵심 요소는 h이고, h는 상수이고, 다른 h를 설정하여 이 점프의 간격을 변경할 수 있기 때문입니다. 그리고 명확한 설명은 없습니다. h가 최상의 효과를 얻기 위해 따르는 규칙은 무엇입니까? (보통 우리는 3*h+1, 즉 1, 4, 13, 40, 121, 364를 사용할 수 있습니다. 이 숫자 그룹은 다음과 같습니다. 시간). h를 결정할 수 없으므로 최적의 시간은 없습니다.

3. 실제 적용

중형 배열의 경우 Hill 정렬의 실행 시간이 허용되기 때문에 숙련된 프로그래머가 Hill 정렬을 사용하는 경우가 있습니다. 코드의 양이 매우 적고 추가 메모리 공간이 사용되지 않습니다. 어쩌면 우리는 더 빠른 알고리즘을 가지고 있을 수도 있지만 N이 큰 경우 Hill 정렬보다 두 배도 채 안 빠릅니다. 그리고 그것은 매우 복잡합니다. 정렬이 필요하지만 체계적인 정렬 기능이 없다면 Hill 정렬을 사용해보고, 좀 더 발전된 정렬 방법으로 대체할지 고민해볼 수도 있습니다.

프로그램 = 데이터 구조 + 알고리즘. 우리가 작성하지 않은 프로젝트를 구축하는 프레임워크의 경우 실제로 프로젝트 수준을 판단할 수 있는 것은 우리가 사용자 정의한 데이터 구조가 편리하고 간결하며 이러한 방법을 구현하는 데 사용하는 알고리즘이 빠른지 여부입니다. 그리고 효과적입니다. 오류가 발생하기 쉽습니다. 만약 당신이 하고 싶은 일이 매일 아침부터 밤까지 벽돌을 옮기는 일이 아니라면, 알고리즘을 배우고 데이터 구조를 분석하는 것이 확실히 레벨을 높이는 유일한 방법입니다.

위는 자바 알고리즘(1) - 1차 정렬 알고리즘의 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(m.sbmmt.com)를 참고해주세요!