SortedAlgorithmTree

排序算法技术研究

排序算法时间复杂度、空间复杂度、稳定性比较

https://blog.csdn.net/yushiyi6453/article/details/76407640

###冒泡排序

void BubbleSort(int array[], int n)
{
    int i, j, k;
    for(i=0; iarray[j+1])
            {
                k=array[j];
                array[j]=array[j+1];
                array[j+1]=k;
            }
        }
}

###选择排序选择排序从小到大排序：一开始从0~~n-1区间上选择一个最小值，将其放在位置0上，然后在1~~n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。

void selectSort(int array[], int n)
{
    int i, j ,min ,k;
    for( i=0; iarray[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            k=array[min];
            array[min]=array[i];
            array[i]=k;
        }
    }
}

###插入排序

插入排序从小到大排序：首先位置1上的数和位置0上的数进行比较，如果位置1上的数大于位置0上的数，
将位置0上的数向后移一位，将1插入到0位置，否则不处理。位置k上的数和之前的数依次进行比较，如果
位置K上的数更大，将之前的数向后移位，最后将位置k上的数插入不满足条件点，反之不处理。

void insertSort(int array[], int n)
{
    int i,j,temp;
    for( i=1;itemp;j--)
            {
                array[j]=array[j-1];
            }
            array[j]=temp;
        }
    }
}

###归并排序

归并排序从小到大排序：首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，
得到长度为2的有序区间，依次进行，直到合成整个区间。

//归并排序复杂度分析：一趟归并需要将待排序列中的所有记录  
//扫描一遍，因此耗费时间为O(n),而由完全二叉树的深度可知，  
//整个归并排序需要进行[log2n],因此，总的时间复杂度为  
//O(nlogn),而且这是归并排序算法中平均的时间性能  
//空间复杂度：由于归并过程中需要与原始记录序列同样数量级的  
//存储空间去存放归并结果及递归深度为log2N的栈空间，因此空间  
//复杂度为O(n+logN)  
//也就是说，归并排序是一种比较占内存，但却效率高且稳定的算法

###快速排序

快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在
左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。

###堆排序

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中
的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，
再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

###希尔排序

希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间
隔步长进行比较并交换，直至步长为1，步长选择是关键。

###桶排序

桶排序是计数排序的变种，把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进
行排序（一般用快排），然后合并成最后的结果。

qiuqiuxiaomaomi/SortedAlgorithmTree

SortedAlgorithmTree