數據結構排序方法有很多，動力節點小編來給大家進行總結。

插入排序

1.直接插入排序：

//直接插入排序時間復雜度：O（n*n）;空間復雜度：O(1);穩定的（指相同元素相對位置不變）
void insertSort(int A[], int n){
         int i, j;
         for (i = 1; i <n; i++){         
                   int tmp = A[i];
                   for (j = i - 1; j >= 0 && tmp < A[j]; j--)                       
                            A[j + 1] = A[j];          
                   A[j + 1] = tmp;
         }
}

2.折半插入排序：

//折半插入排序  時間復雜度：O（n*n）空間復雜度：O（1）穩定的
void insertSort(int A[], int n){
         int i, j,high,low,mid;
         for (i = 1; i < n; i++){
                   int tmp = A[i];
                   low = 0; high = i - 1;
                   while (low<=high)
                   {
                            mid = (low + high)/ 2;
                            if (A[mid] > tmp) high = mid - 1;
                            else low = mid + 1;
                   }
                   for (j = i - 1; j >high; j--)
                            A[j + 1] = A[j];
                   A[high+1] = tmp;
         }
}

3.希爾排序：

//希爾排序時間復雜度：O（n*n）空間復雜度：O（1）不穩定
void shellSort(int A[], int n){
         int i, j, dk;
         for (dk = n / 2; dk >= 1; dk = dk / 2){
                   for (i = dk; i < n; ++i){
                            int tmp = A[i];
                            for (j = i - dk; j >= 0 && tmp < A[j]; j -= dk)
                                     A[j + dk] = A[j];
                            A[j + dk] = tmp;
                   }
         }
}

總結：

直接插入排序時間分為三部分：n次遍歷、后移次數、比較次數，折半插入排序減少了比較次數，希爾排序可能減少了比較和后移次數;

交換排序

1.冒泡排序：

//冒泡排序  時間復雜度：O（n*n)  空間復雜度：O（1）穩定的
void bubbleSort(int A[], int n){
         int i, j;
         bool flag;
         for (i = 0; i < n - 1; i++){
                   flag = false;
                   for (j = n - 1; j > i; j--){
                            if (A[j] < A[j - 1]){
                                     swap(A[j-1],A[j]);
                                     flag = true;
                            }
                   }
                   if (!flag){
                            return;
                   }
         }
}

2.快速排序：

//快速排序時間復雜度：O（N*log2 N）空間復雜度：O（1）不穩定
int partition_(int A[], int low, int high){
         int p = A[low];
         while (low<high)
         {
                   while (low<high&&A[high] > p) high--;
                   while (low<high&&A[low] < p) low++;
                   if (low < high){
                            swap(A[low], A[high]);
                            if (A[low] == p&&A[high] == p)
                                     low++;
                   }
         }
         A[low] = p;
         return low;
}
void quickSort(int A[], int low, int high){
         if (low < high){
                   int pivotpos = partition_(A, low, high);
                   quickSort(A,low,pivotpos -1);
                   quickSort(A,pivotpos+1,high);
         }
}

選擇排序

1.簡單選擇排序：

//簡單選擇排序  時間復雜度： O（n*n）空間復雜度：O（1）不穩定的
void selectSort(int A[], int n){
         int i, j, min;
         for (i = 0; i < n-1; i++){
                   min = i;
                   for (j = i + 1; j < n; j++)
                            if (A[j]<A[min]) min = j;           
                   if (min != i) swap(A[i], A[min]);
         }
}

2.堆排序：

//堆排序  時間復雜度：O（N*log2N）空間復雜度：O（1）不穩定的
void adjustDown(int A[], int k, int len){
         int tmp = A[k];
         for (int i = 2 * k + 1; i < len; i = 2 * i + 1){
                   if (i<len - 1 && A[i] < A[i + 1])
                            i++;
                   if (tmp >= A[i])  break;
                   if (A[i] > tmp){
                            A[k] = A[i];
                            k = i;
                   }
         }
         A[k] = tmp;
}
void buildMaxHead(int A[], int len){
         int i;
         for (i = len / 2-1; i >=0; i--)
                   adjustDown(A,i,len);        
}
void heapSort(int A[], int len){
         buildMaxHead(A,len);    
         for (int i = len - 1; i > 0; i--){
                   swap(A[i],A[0]);
                   adjustDown(A,0,i);
         }
}
//向上調整
void adjustUp(int A[], int k){
         int tmp = A[k];
         int i = k / 2;
         while (i >= 0 && tmp > A[i]){
                   A[k] = A[i];
                   k = i;
                   i = i / 2;
         }
         A[k] = tmp;
}

二路歸并排序

//二路歸并排序時間復雜度O（N*log2N）空間復雜度O(n)  穩定的
int n = 10;
int* B = (int*)malloc((n + 1)*sizeof(int));
void merge(int A[], int low, int mid, int high){
         int i, j, k;
         for (k = low; k <= high; k++)
                   B[k] = A[k];
         for (i = low, j = mid + 1, k = i; i <= mid&&j <= high;k++){
                   if (B[i] <= B[j])
                            A[k] = B[i++];
                   else
                            A[k] = B[j++];
         }
         while (i <= mid) A[k++] = B[i++];
         while (j <= high) A[k++] = B[j++];   
}
void mergeSort(int A[],int low,int high){
         if (low < high){
                   int mid = (low + high) / 2;
                   mergeSort(A,low,mid);
                   mergeSort(A,mid+1,high);
                   merge(A, low, mid, high);
         }
}

以上就是關于“數據結構排序算法總結”介紹，大家如果對此比較感興趣，想了解更多相關知識，可以關注一下動力節點的Java在線學習，里面的課程從入門到精通，細致全面，很適合沒有基礎的小伙伴學習，希望對大家能夠有所幫助哦。