Java 基本排序算法

我会带着你远行 2023-10-18 23:40 35阅读 0赞

#### 文章目录 ####

*  1. 算法的性能
 *   *   *  排序算法稳定性：
 *  2. 算法的实现
 *   *   *  2.1. 冒泡排序
         *   *   *  算法步骤：
         *  2.2. 选择排序
         *   *   *  算法步骤：
         *  2.3. 直接插入排序
         *   *   *  算法步骤：
         *  2.4. 堆排序
         *   *   *  算法步骤:
         *  2.5. 两路合并排序
         *   *   *  算法步骤:
         *  2.6. 快速排序
         *   *   *  算法步骤:
                 *  辅助方法 swap:

## 1. 算法的性能 ##

#### 排序算法稳定性： ####

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的.**即在原序列中，array\[i\]==array\[j\]，且 i<j，而在排序后的序列中，array\[i\] 仍在 array\[j\]之前**。

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>平均时间复杂度</th> 
   <th>最好时间</th> 
   <th>最坏时间</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡</td> 
   <td>O（n ^2）</td> 
   <td>O(n)</td> 
   <td>O（n ^2）</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>简单选择</td> 
   <td>O（n ^2）</td> 
   <td>O(n)</td> 
   <td>O（n ^2）</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>直接插入</td> 
   <td>O（n ^2）</td> 
   <td>O(n)</td> 
   <td>O（n ^2）</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O（nlog n）</td> 
   <td>O(nlog n)</td> 
   <td>O（nlog n）</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>两路合并</td> 
   <td>O（nlog n）</td> 
   <td>O(nlog n)</td> 
   <td>O（nlog n）</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快排</td> 
   <td>O（nlog n）</td> 
   <td>O(nlog n)</td> 
   <td>O（n ^2）</td> 
   <td>O(nlog n) ~ O（∞）</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

来源 ：《算法设计与分析》- 陈慧南版 P.81 表 5-2

## 2. 算法的实现 ##

#### 2.1. 冒泡排序 ####

###### 算法步骤： ######

1.  比较相邻的元素。如果第一个比第二个大，就交换位置。
2.  对每一组相邻元素作同样的操作，从开始第一组到结尾的最后一组。
3.  针对所有的元素重复以上的步骤，每一趟最大元素冒到需排序元素的尾部，故比较范围在减小。
4.  对每趟都在减少的需排序元素重复上面的步骤，直到没有任何一对数字需要比较。

**冒泡排序最好情况原数组有序，时间为 O（n）,最大的元素冒到数组末尾。**

public void bubbleSort(int a[]) {
        
    		int length = a.length;
    		for (int i = 0; i < length - 1; i++) {
          // 共有 n 个元素，也就需要比较 n-1 趟
    			for (int j = 0; j < length - 1 - i; j++) {
        //数组尾部存放的元素已经有序，比较范围在缩小
    				if (a[j] > a[j + 1]) {
        
    					swap(a, j, j+1);
    				}
    			}
    		}
    	}

#### 2.2. 选择排序 ####

###### 算法步骤： ######

1.  在未排序序列中找到最小元素，存放到排序序列的起始位置.
2.  从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
3.  重复以上步骤,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动.

public void selectSort(int a[]) {
        
    		for (int i = 0; i < a.length - 1; i++) {
        
    			int minIndex = i;
    			for (int j = i + 1; j < a.length; j++) {
        
    				if (a[j] < a[i]) {
        
    					minIndex = j; // 每次选择未排序序列中最小值
    				}
    			}
    			if (minIndex != i) {
        
    				swap(a, minIndex, i); // 放到数组头部已排序部分的末尾
    			}
    		}
    	}

#### 2.3. 直接插入排序 ####

###### 算法步骤： ######

1.  构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到应插入位置。
2.  反复把已排序元素逐步向后挪位，为最新元素提供插入空间, 并插入正确位置.
3.  重复以上步骤,直至元素遍历完毕.

public void insertSort(int a[]) {
        
    		for (int i = 0;i <a.length;i++) {
        
    			int get = a[i]; // 默认 a[0]为排序好的元素
    			int j = i-1;
    			while (j >= 0 && a[j] >get) {
        // a[i] 需要往有序序列插入，序列中大于 get 的元素需往后移动，挪出位置
    				a[j+1]= a[j];
    				j--;
    			}
    			a[j+1] = get; // 插入正确位置
    		}
    	}

#### 2.4. 堆排序 ####

简单的公式描述一下堆的定义就是：  
大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  
小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]

###### 算法步骤: ######

1.  将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2.  将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3.  重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

// 堆调整方法
    public void heapify(int a[], int i, int size) {
        //从a[i]向下调整堆
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            int max = i;
            //找父节点和两个子节点中的最大值，确保父节点为最大值
            if (leftChild < size && a[leftChild] > a[max])
                max = leftChild;
            if (rightChild < size && a[rightChild] > a[max])
                max = rightChild;
            if (max != i) {
        
                swap(a, i, max);
                heapify(a, max, size);//记录交换前子节点位置，从该位置向下调整堆
            }
        }
    
        //建最大堆方法,堆顶为数组中最大元素
        public int buildHeap(int a[], int n) {
        
            int heapSize = n;
            for (int i = heapSize / 2 - 1; i >= 0; i--) {
        //从非叶子结点开始调整，直到a[0]根
                heapify(a, i, heapSize);
            }
            return heapSize;
        }
        
        //堆排序方法
        public void heapSort(int a[], int n) {
        
            int heapSize = buildHeap(a, n);
            while (heapSize > 1) {
        
                // 将堆顶元素与堆的最后一个元素互换，并将最后一个元素从以后的堆调整中忽略--heap_size
                swap(a, 0, --heapSize);
                heapify(a, 0, heapSize);//从新的堆顶调整堆
            }
        }

#### 2.5. 两路合并排序 ####

###### 算法步骤: ######

1.  将有n个元素的序列不断划分为n个长度为1的有序子序列.
2.  两两合并子序列，直到得到一个长度为n的有序序列时结束。

public void mergeSort(int a[], int left, int right) {
        
            if (left == right) return;
            int mid = (left + right) / 2;  // 1. 不断将数组分划为两路子序列
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right); // 2.归并数组
        }
    
       //按照规则归并数组
        public void merge(int a[], int left, int mid, int right) {
        
            int len = right - left + 1;
            int temp[] = new int[len];
            int index = 0;
            int i = left, j = mid + 1;
            while (i <= mid && j <= right) {
        
                temp[index++] = a[i] <= a[j] ? a[i++] : a[j++];
            }//左右两部分长度不一样时的处理
            while (i <= mid) {
        
                temp[index++] = a[i++];
            }
            while (j <= right) {
        
                temp[index++] = a[j++];
            }
            for (int k = 0; k < len; k++) {
        
                a[left++] = temp[k];//把排序好的数组赋值给原数组
            }
        }

#### 2.6. 快速排序 ####

###### 算法步骤: ######

1.  选定数组最左边的元素为比较基点 target.
2.  双指针思想,左指针从左往右查找比 target 大的元素下标 i , 右指针从右往左查找比 target 小的元素下标 j, 如果 i < j 成立说明一趟遍历未结束, 交换两元素位置.
3.  一趟遍历完毕,交换当前比较基点 target 和 右指针下标.当前数组**右指针下标元素变为target**,以其分界,左边都是比 target 小的元素, 右边都是比target 大的元素, 将数组划分为两部分,重复以上步骤.

//快排
        public void quickSort(int a[], int left, int right) {
        
            int i, j;
            while (left < right) {
        
                i = left;
                j = right + 1;
                do {
        
                    while (a[++i] < a[left]) ;
                    while (a[--j] > a[left]) ;
                    if (i < j) swap(a, i, j);//从左往右找比标记元素大,从右往左找比标记元素小,交换
                } while (i < j);
                swap(a, left, j);//一趟完毕，交换标记元素位置
                quickSort(a, left, j - 1);
                quickSort(a, j + 1, right);
                return;
            }
        }

###### 辅助方法 swap: ######

private void swap(int a[], int i, int j) {
        
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }