不稳定排序算法

一 简单选择排序算法

下图为简单选择排序的实现过程:

图片来自网络

 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 void SelectSort(int *data,int n){
  5 
  6   int k; // 找到最小元素的下标
  7   int temp;
  8   for(int i = 0; i < n - 1; i++){
  9 
 10       k = i;
 11 
 12       for(int j = i + 1; j < n; j++){
 13 
 14          if(data[k] >  data[j]) k = j;
 15       }
 16 
 17       if(k != i){
 18         temp = data[i];data[i] = data[k];data[k] = temp;
 19       }
 20 
 21   }
 22 
 int main(int argc,char *argv[]){
 27 
 28  int data[] = {5,2,3,1,4};
 29 
 30  SelectSort(data,4);
 31 
 32  for (int i = 0; i < 4;i++){
 33 
 34   printf("%d   ",data[i]);
 35 
 36  }
 37  return 0;
 38 
 39 }

二 希尔排序

希尔排序是对直接插入排序的改进,基本思想是:将整个序列分成若干个序列,然后对这些子序列进行直接插入排序,待有序时,对整体序列进行一次直接插入排序,时间复杂度为0(n^1.3)
例如:初始关键码 48 37 64 96 75 12 26 48(-) 54 3
设置增量 10/2 = 5 5/2 = 3 3/2 = 1

image.png

#include<stdio.h>
#include<stdlib.h>

void shellSort(int *data,int n,int delta[],int m){
  int temp,dk,j,k;

  for(int i = 0; i < m;i++ ){
     
     dk = delta[i];

     for( k = dk; k < n; k++ ){
         
     if(data[k] < data[k-dk]){
             temp = data[k];
             data[k] = data[k- dk];
         for( j = k - dk;j >=0 && temp < data[j];j-=dk){
                 data[j + dk]  = data[j];
         }

         data[j + dk] = temp;
    
     }

     }
  }
}

int main(int argc,char *argv[]){

 int data[] = {48,37,64,96,75,12,26,48,54,3};
 int  n = 10;
 int delta[] = {10/2,10/4,10/8};
 int m = 3;
 shellSort(data,n,delta,m);

 for(int i = 0;i < n; i++){
   printf("%d ",data[i]);
 }
 return 0;
}

3 快速排序

/// 快速排序 空间复杂度为0(log2n)
/// - Parameters:
///   - a: <#a description#>
///   - low: <#low description#>
///   - high: <#high description#>
func qulickSort(a: inout [Int], low:Int,high:Int){
    
    if low >= high {
        return
    }
    
    var i = low;
    var j = high;
    // 基准值
    let base = a[i];
    
    while i < j {
        // 从右边开始 找到一个比base小 然后交换
        while i < j && a[j] >= base {
            j -= 1
        }
        a[i] = a[j]
        
        // 从左边开始 找到比base大 然后进行交换
        while i < j && a[i] <= base {
            i += 1
        }
        a[j] = a[i]
        
    }
    
    a[i] = base
    // 左递归
    qulickSort(a: &a, low: low, high: i - 1)
    // 右递归
    qulickSort(a: &a, low: i + 1, high: high)
    
}