BUG: Preserve index order when constructing DataFrame from dict
- [x] closes #24859
- [x] tests added / passed
    (no new tests added)
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

This resolves the issue of `pd.DataFrame(dict)` or `pd.DataFrame.from_dict(dict)` not preserving the order of the index specified in `dict`.

This required fixing up tests that relied on alphabetical ordering. The changes to these tests also test for this new preserved ordering; let me know if I should add an additional explicit test.
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=h1) Report
> Merging [#26113](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/68b1da7f53f043b21e3f722e8872e19941a10250?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26113/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26113      +/-   ##
==========================================
- Coverage   91.99%   91.98%   -0.01%     
==========================================
  Files         175      175              
  Lines       52384    52385       +1     
==========================================
- Hits        48189    48186       -3     
- Misses       4195     4199       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.53% <100%> (ø)` | :arrow_up: |
| #single | `40.73% <100%> (-0.14%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/api.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9hcGkucHk=) | `99.01% <100%> (ø)` | :arrow_up: |
| [pandas/core/internals/construction.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW50ZXJuYWxzL2NvbnN0cnVjdGlvbi5weQ==) | `95.88% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `75% <0%> (-12.5%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.9% <0%> (-0.12%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=footer). Last update [68b1da7...f9d82eb](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 # [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=h1) Report
> Merging [#26113](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/68b1da7f53f043b21e3f722e8872e19941a10250?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/26113/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #26113      +/-   ##
==========================================
- Coverage   91.99%   91.98%   -0.01%     
==========================================
  Files         175      175              
  Lines       52384    52385       +1     
==========================================
- Hits        48189    48186       -3     
- Misses       4195     4199       +4
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.53% <100%> (ø)` | :arrow_up: |
| #single | `40.73% <100%> (-0.14%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `96.9% <ø> (-0.12%)` | :arrow_down: |
| [pandas/core/indexes/api.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9hcGkucHk=) | `99.01% <100%> (ø)` | :arrow_up: |
| [pandas/core/internals/construction.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW50ZXJuYWxzL2NvbnN0cnVjdGlvbi5weQ==) | `95.88% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `75% <0%> (-12.5%)` | :arrow_down: |
| [pandas/core/tools/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvdG9vbHMvZGF0ZXRpbWVzLnB5) | `84.59% <0%> (ø)` | :arrow_up: |
| [pandas/core/window.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvd2luZG93LnB5) | `96.39% <0%> (ø)` | :arrow_up: |
| [pandas/core/groupby/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/26113/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ3JvdXBieS9nZW5lcmljLnB5) | `89.02% <0%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=footer). Last update [68b1da7...adff27b](https://codecov.io/gh/pandas-dev/pandas/pull/26113?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 PTAL The more I am looking at this the less I am thinking we can actually support this. We had a similar discussion here:

https://github.com/pandas-dev/pandas/pull/25915#issuecomment-478278485

The original issue being linked is pretty explicit about `orient='index'` which I think could work in and of itself since index items would always be the keys in the top level dict, but this PR is starting to stray further down into nested dicts which I don't think is generalizable. 

For instance, what is the expectation if this occurs:

```python
data = {
    'A': {'bar': 0, 'foo': 1},
    'B': {'foo': 0, 'bar': 1}
}
pd.DataFrame(data)
```

Even this one modified in the PR gets a little suspect:

```python
df.agg({'A' : ['max', 'min'], 'B' : ['min', 'sum']})
```

 I thought this was a bug because the API was changed to follow insertion order in https://github.com/pandas-dev/pandas/pull/25915 (https://pandas.pydata.org/pandas-docs/stable/whatsnew/v0.23.0.html#instantiation-from-dicts-preserves-dict-insertion-order-for-python-3-6).

I agree the example of mismatched dictionary indexes is not clear and the choice will either be arbitrary (order of first dict, which is what the behavior would be under this PR), or will be a special case (fall back to sorting?)

But one case where following insertion order is useful is for round-tripping the conversion of a DataFrame to/from a dict. E.g. `df.equals(pd.DataFrame(df.to_dict()))`, and the same for round-tripping to/from json (`to_json` and `read_json`). Yea so the distinction I was trying to make before was that we can make guarantees about ordering from the top most level of the dict, but making guarantees about nested dicts probably isn't feasible.

> But one case where following insertion order is useful is for round-tripping the conversion of a DataFrame to/from a dict. E.g. `df.equals(pd.DataFrame(df.to_dict()))`, and the same for round-tripping to/from json (`to_json` and `read_json`).

I think the former here holds True so long as you are only dealing with one top level dictionary. Standard JSON objects by definition have no order so there's no way to explicitly support the latter (though it may be implicitly or through alternate specifications like the table schema) Making guarantees about nested dicts would still be needed for round-tripping. If the top-level of `df.to_dict()` were the DataFrame's index, then the nested level would be the columns, and so the columns of `pd.DataFrame(df.to_dict())` will still end up in a different order than the original dataframe `df`. > Making guarantees about nested dicts would still be needed for round-tripping. If the top-level of df.to_dict() were the DataFrame's index, then the nested level would be the columns, and so the columns of pd.DataFrame(df.to_dict()) will still end up in a different order than the original dataframe df.

round-tripping with unordered things is not guaranteed at all, nor are why trying to 'fix' it. If you need a guarantee then you need to use lists which guarantee ordering. It is an implementation detail that python happens to guarantee insertion order starting in 3.6, this is certainly not true for anything JSON. Insertion order is publicly guaranteed for dicts starting with Python 3.7 Thanks for the PR @bchu ! I think based on discussion above though that there isn't a huge appetite for this one at the moment and going to close as is. 

Certainly welcome contributions on other outstanding issues if you have any you'd like to tackle