数据结构排序算法总结

数据结构排序方法有很多，极悦小编来给大家进行总结。

插入排序

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极悦在线学习，里面的课程从入门到精通，细致全面，很适合没有基础的小伙伴学习，希望对大家能够有所帮助哦。